问题一:
正确实现的拓扑排序的正确运行时间应该是多少。我看到了不同的意见:
问题二:
我的实现运行时间为 O(V*E)。因为在最坏的情况下,我将需要遍历图表 E 次,每次我都需要检查 V 项。如何将我的实现变成线性时间。
该算法按步骤工作:
- 以邻接表的形式生成图
例如这个图
0 - - 2
\
1 -- 3
产生这个邻接表
{0: [], 1: [0], 2: [0], 3: [1, 2]}
0 不依赖于任何东西,1 依赖于 0 等等。
- 遍历图并找到没有任何依赖关系的节点
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 实现。
