Skip to main content
 首页 » 编程设计

python之如何使我的拓扑排序成为线性时间 (代码注释很好)

2024年10月24日1652php

问题一:

正确实现的拓扑排序的正确运行时间应该是多少。我看到了不同的意见:

Wikipedia says: O(log^2(n))

Geeksforgeeks says: O(V+E)

问题二:

我的实现运行时间为 O(V*E)。因为在最坏的情况下,我将需要遍历图表 E 次,每次我都需要检查 V 项。如何将我的实现变成线性时间。


该算法按步骤工作:

  1. 以邻接表的形式生成图

例如这个图

0 - - 2 
    \ 
      1 -- 3 

产生这个邻接表

{0: [], 1: [0], 2: [0], 3: [1, 2]} 

0 不依赖于任何东西,1 依赖于 0 等等。

  1. 遍历图并找到没有任何依赖关系的节点

def produce_graph(prerequisites): 
    adj = {} 
    for course in prerequisites: 
        if course[0] in adj: 
            # append prequisites 
            adj[course[0]].append(course[1]) 
        else: 
            adj[course[0]] = [course[1]] 
 
        # ensure that prerequisites are also in the graph 
        if course[1] not in adj: 
            adj[course[1]] = [] 
 
    return adj 
 
def toposort(graph): 
    sorted_courses = [] 
    while graph: 
 
        # we mark this as False 
        # In acyclic graph, we should be able to resolve at least 
        # one node in each cycle 
        acyclic = False 
        for node, predecessors in graph.items(): 
            # here, we check whether this node has predecessors 
            # if a node has no predecessors, it is already resolved, 
            # we can jump straight to adding the node into sorted 
            # else, mark resolved as False 
            resolved = len(predecessors) == 0 
            for predecessor in predecessors: 
                # this node has predecessor that is not yet resolved 
                if predecessor in graph: 
                    resolved = False 
                    break 
                else: 
                    # this particular predecessor is resolved 
                    resolved = True 
 
            # all the predecessor of this node has been resolved 
            # therefore this node is also resolved 
            if resolved: 
                # since we are able to resolve this node 
                # We mark this to be acyclic 
                acyclic = True 
                del graph[node] 
                sorted_courses.append(node) 
 
        # if we go through the graph, and found that we could not resolve 
        # any node. Then that means this graph is cyclic 
        if not acyclic: 
            # if not acyclic then there is no order 
            # return empty list 
            return [] 
 
    return sorted_courses 
 
graph = produce_graph([[1,0],[2,0],[3,1],[3,2]]) 
print toposort(graph) 

请您参考如下方法:

好的,这是个好问题。只要图是有向无环的,就可以使用深度优先搜索,深度优先搜索的阶数为 O(n+m),如下所述:http://www.csd.uoc.gr/~hy583/reviewed_notes/dfs_dags.pdf 如果您好奇 networkx 有一个使用深度优先搜索的实现,它称为 topological_sort,它有源代码可用于查看 python 实现。