Python递归实现拓扑排序算法

2023-04-16 00:00:00 算法 递归 拓扑

拓扑排序是一种常见的图算法，用于对有向无环图（DAG）进行排序。其基本思想是找出图中没有入度的节点，将其加入排序结果中，并将与该节点相邻的节点的入度减1。重复该过程直到所有节点都被排序完成。如果图中存在环，则无法进行拓扑排序。
Python递归实现拓扑排序的方法比较简单，其大致思路如下：
1. 构建图的邻接表，并计算每个节点的入度。
2. 遍历所有节点，将入度为0的节点加入排序结果中。
3. 对于每个已加入排序结果中的节点，遍历其邻接节点，将其入度减1。
4. 递归调用拓扑排序函数，直到所有节点都被加入排序结果中。
下面是具体的代码演示：

#构建邻接表，计算入度
def build_adj_list(n, edges):
    adj_list = [[] for i in range(n)]
    in_degrees = [0] * n
    for edge in edges:
        adj_list[edge[0]].append(edge[1])
        in_degrees[edge[1]] += 1
    return adj_list, in_degrees
#递归实现拓扑排序
def topo_sort_util(node, adj_list, in_degrees, visited, result):
    visited[node] = True
    result.append(node)
    for adj_node in adj_list[node]:
        in_degrees[adj_node] -= 1
        if in_degrees[adj_node] == 0 and not visited[adj_node]:
            topo_sort_util(adj_node, adj_list, in_degrees, visited, result)
#拓扑排序主函数
def topo_sort(n, edges):
    adj_list, in_degrees = build_adj_list(n, edges)
    visited = [False] * n
    result = []
    for i in range(n):
        if in_degrees[i] == 0 and not visited[i]:
            topo_sort_util(i, adj_list, in_degrees, visited, result)
    return result

这是一个比较简单的代码实现，大致思路已经介绍清楚了。在实际使用中，可能需要考虑更加复杂的情况，比如并行任务的拓扑排序等，需要根据具体场景进行相应的修改。

相关文章