python toposort

在Python中，Toposort（拓扑排序）是一种算法，它用于对有向无环图（DAG，Directed Acyclic Graph）中的节点进行排序，保证对于任意一条从u到v的边，排序后的列表中节点u总是在节点v之前。这种排序可以用于解决依赖关系问题，例如任务调度、模块加载顺序等。

`python-toposort`是一个第三方库，提供了一种方便的方式来实现toposort功能。使用这个库，你可以按照以下步骤：

1. 首先安装库：`pip install toposort`
2. 导入toposort模块：

from toposort import toposort_flatten

3. 创建一个表示依赖关系的字典或类似结构，其中键是元素，值是其依赖的元素集合：

dependencies = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': [],
    'D': []
}

4. 调用`toposort_flatten`函数来进行排序：

sorted_dependencies = toposort_flatten(dependencies)

`sorted_dependencies`将返回一个列表，按照拓扑排序的顺序排列。

相关问题

递归实现拓扑排序python

可以使用深度优先搜索（DFS）算法对有向无环图（DAG）进行拓扑排序。先进行DFS遍历，对于每个节点，记录其访问状态，分为三种：未访问、正在访问和已访问。每当遍历到一个节点时，将其状态设置为正在访问，然后对其所有未访问的邻居进行DFS遍历。如果邻居节点已经被访问过了，则说明存在环，直接return。当所有邻居节点都被访问过后，将该节点状态设置为已访问，并将其加入结果列表中。最后逆序输出结果列表即可得到拓扑排序结果。

以下是递归实现的Python代码：

from collections import defaultdict

def topoSort(node, graph, visited, result):
    visited[node] = 1
    for neighbor in graph[node]:
        if visited[neighbor] == 0:
            topoSort(neighbor, graph, visited, result)
        elif visited[neighbor] == 1:
            # 如果邻居节点已经被访问过了，说明存在环，直接return
            return
    visited[node] = 2
    result.append(node)

def topoSortDFS(graph):
    visited = defaultdict(int)
    result = []

    for node in graph.keys():
        if visited[node] == 0:
            topoSort(node, graph, visited, result)

    return result[::-1]

其中，graph为邻接表表示的有向无环图。结果列表中的节点顺序即为拓扑排序后的结果。

#include "stdio.h" #include "stdlib.h" #include "malloc.h" #define Null 0 #define MAX 20 typedef struct ArcNode { int adjvex; int weight; struct ArcNode *nextarc; }ArcNode,*AdjList; typedef struct Graph { AdjList elem[MAX+1]; int vexnum; int arcnum; int GraphKind; }Graph; typedef struct Stack { int s[MAX]; int top; }Stack; void initStack(Stack *s) { (*s).top=0; } int Push(Stack *s, int e) { if((*s).top>=MAX) return 0; else (*s).s[(*s).top++]=e; } int Pop(Stack *s, int *e) { if((*s).top<=0) return 0; else *e=(*s).s[--(*s).top]; } int StackEmpty(Stack s) { if(s.top==0)return 1; else return 0; } void create(Graph *G) { int i, start, end; AdjList p; for(i=0;i<=MAX;i++) (*G).elem[i]=Null; for(i=1;i<=(*G).arcnum;i++) { scanf("%d,%d",&start,&end); p=(AdjList)malloc(sizeof(ArcNode)); p->adjvex=end; p->nextarc=(*G).elem[start]; (*G).elem[start]=p; if((*G).GraphKind==0) { p=(AdjList)malloc(sizeof(ArcNode)); p->adjvex=start; p->nextarc=(*G).elem[end]; (*G).elem[end]=p; } } } int TopoSort(Graph G) { } main() { Graph G; printf("Please input the number of vex, arc and GraphKind:"); scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.GraphKind); create(&G); printf("The outcome of TopoSort is:\n"); TopoSort(G); }

这段代码是一个基于邻接表存储结构的有向图的拓扑排序的程序框架。但是其中的 TopoSort 函数还没有实现，需要我们来完成。

拓扑排序的算法是基于 Kahn 算法的。其基本思想是不断地选择入度为 0 的顶点，并将其从图中删除，直到所有顶点都被选择为止。在实现过程中，我们需要使用一个队列来存储入度为 0 的顶点。

在这个程序中，我们可以将入度为 0 的顶点入栈，然后依次出栈并处理它们的邻接节点，更新它们的入度。具体实现细节可以参考下面的代码。

int TopoSort(Graph G) {
    int i, e, cnt = 0;
    int *indegree = (int *)malloc(sizeof(int) * (G.vexnum + 1));
    Stack s;
    initStack(&s);
    for (i = 1; i <= G.vexnum; i++) {
        indegree[i] = 0;
    }
    for (i = 1; i <= G.vexnum; i++) {
        AdjList p = G.elem[i];
        while (p != Null) {
            indegree[p->adjvex]++;
            p = p->nextarc;
        }
    }
    for (i = 1; i <= G.vexnum; i++) {
        if (indegree[i] == 0) {
            Push(&s, i);
        }
    }
    while (!StackEmpty(s)) {
        Pop(&s, &e);
        printf("%d ", e);
        cnt++;
        AdjList p = G.elem[e];
        while (p != Null) {
            indegree[p->adjvex]--;
            if (indegree[p->adjvex] == 0) {
                Push(&s, p->adjvex);
            }
            p = p->nextarc;
        }
    }
    if (cnt != G.vexnum) {
        printf("Error: the graph has a cycle.\n");
        return 0;
    }
    return 1;
}

上面的代码实现了基于邻接表存储结构的有向图的拓扑排序。其中使用了一个栈来存储入度为 0 的顶点，使用了一个数组来存储每个顶点的入度。如果拓扑排序成功，会输出拓扑排序序列；如果图中存在环，会输出错误信息。

完整的程序如下：

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"

#define Null 0
#define MAX 20

typedef struct ArcNode {
    int adjvex;
    int weight;
    struct ArcNode *nextarc;
} ArcNode, *AdjList;

typedef struct Graph {
    AdjList elem[MAX + 1];
    int vexnum;
    int arcnum;
    int GraphKind;
} Graph;

typedef struct Stack {
    int s[MAX];
    int top;
} Stack;

void initStack(Stack *s) {
    (*s).top = 0;
}

int Push(Stack *s, int e) {
    if ((*s).top >= MAX)
        return 0;
    else
        (*s).s[(*s).top++] = e;
}

int Pop(Stack *s, int *e) {
    if ((*s).top <= 0)
        return 0;
    else
        *e = (*s).s[--(*s).top];
}

int StackEmpty(Stack s) {
    if (s.top == 0)
        return 1;
    else
        return 0;
}

void create(Graph *G) {
    int i, start, end;
    AdjList p;
    for (i = 0; i <= MAX; i++)
        (*G).elem[i] = Null;
    for (i = 1; i <= (*G).arcnum; i++) {
        scanf("%d,%d", &start, &end);
        p = (AdjList) malloc(sizeof(ArcNode));
        p->adjvex = end;
        p->nextarc = (*G).elem[start];
        (*G).elem[start] = p;
        if ((*G).GraphKind == 0) {
            p = (AdjList) malloc(sizeof(ArcNode));
            p->adjvex = start;
            p->nextarc = (*G).elem[end];
            (*G).elem[end] = p;
        }
    }
}

int TopoSort(Graph G) {
    int i, e, cnt = 0;
    int *indegree = (int *) malloc(sizeof(int) * (G.vexnum + 1));
    Stack s;
    initStack(&s);
    for (i = 1; i <= G.vexnum; i++) {
        indegree[i] = 0;
    }
    for (i = 1; i <= G.vexnum; i++) {
        AdjList p = G.elem[i];
        while (p != Null) {
            indegree[p->adjvex]++;
            p = p->nextarc;
        }
    }
    for (i = 1; i <= G.vexnum; i++) {
        if (indegree[i] == 0) {
            Push(&s, i);
        }
    }
    while (!StackEmpty(s)) {
        Pop(&s, &e);
        printf("%d ", e);
        cnt++;
        AdjList p = G.elem[e];
        while (p != Null) {
            indegree[p->adjvex]--;
            if (indegree[p->adjvex] == 0) {
                Push(&s, p->adjvex);
            }
            p = p->nextarc;
        }
    }
    if (cnt != G.vexnum) {
        printf("Error: the graph has a cycle.\n");
        return 0;
    }
    return 1;
}

int main() {
    Graph G;
    printf("Please input the number of vex, arc and GraphKind:");
    scanf("%d,%d,%d", &G.vexnum, &G.arcnum, &G.GraphKind);
    create(&G);
    printf("The outcome of TopoSort is:\n");
    TopoSort(G);
    return 0;
}