mot*_*iur 6 algorithm graph directed-acyclic-graphs graph-algorithm data-structures
拓扑排序可以使用 DFS（边缘反转）和队列来完成。BFS 也可以使用队列来完成。使用队列进行 BFS 时元素的存储和检索方式与使用队列进行拓扑排序时的元素存储和检索方式之间是否存在任何关系。澄清会有所帮助。谢谢。
不，没有必然的关系。我假设您指的是wikipedia/Topological_sorting#Algorithms中 Kahn 的算法，维基百科指出：
\n\n\n\n\n请注意，为了反映排序结果的非唯一性，结构 S 可以简单地是集合、队列或堆栈。
\n
因此，拓扑排序的“队列”实际上是“任何集合”结构，并且该集合中的顺序并不重要；它可以是任何东西。另一方面，用于 BFS 的队列则与顺序有关；这样它就可以完成其 FIFO（先进先出）任务。改变这个顺序将会破坏 BFS 算法。
\n\n可能还有其他基于“队列”的拓扑排序算法，其中结构是队列确实很重要。如果您询问特定的此类算法，请澄清。
\n\n编辑：感兴趣的算法被澄清为改进算法部分，与卡恩的相同。
\n\n编辑：我已经编写了一些代码，根据您链接的页面中的改进算法部分实现拓扑排序。我创建了它使用任意集合类型作为排序函数的参数。然后我制作了几种类型的此类集合，包括堆栈、队列、随机弹出集合和 python 集（它是哈希集，因此不保证顺序）。
\n\n然后，我制作一个图表，并在每个集合上测试排序算法。然后我使用维基百科上列出的拓扑排序定义来测试每个结果：
\n\n\n\n\n.. 有向图的拓扑排序（有时缩写为 topsort 或 toposort）或拓扑排序是其顶点的线性排序，使得对于每条边 uv，u 在排序中位于 v 之前。
\n\n\xe2\x80\x95维基百科
\n
代码是用 python 编写的，如下所示。结果来自http://ideone.com。 我不知道生成随机 DAG 进行测试的好简单方法，所以我的测试图很蹩脚。请随意评论/编辑一个好的 DAG 生成器。
\n\n编辑：现在我有一个不太蹩脚的生成器，但它使用networkx。该函数nx_generate_random_dag在代码中，但它在函数中导入了networkx。您可以取消注释 main 中标记的部分来生成图表。我将生成的图表硬编码到代码中，因此我们得到了更有趣的结果。
所有这些都是为了表明，“集合”数据结构（算法中的队列）的顺序可以是任何顺序。
\n\nfrom collections import deque\nimport random\n\n\ndef is_topsorted(V,E,sequence):\n sequence = list(sequence)\n #from wikipedia definition of top-sort\n #for every edge uv, u comes before v in the ordering\n for u,v in E:\n ui = sequence.index(u)\n vi = sequence.index(v)\n if not (ui < vi):\n return False\n return True \n\n#the collection_type should behave like a set:\n# it must have add(), pop() and __len__() as members.\ndef topsort(V,E,collection_type):\n #out edges\n INS = {}\n\n #in edges\n OUTS = {}\n for v in V:\n INS[v] = set()\n OUTS[v] = set()\n\n #for each edge u,v,\n for u,v in E:\n #record the out-edge from u\n OUTS[u].add(v)\n #record the in-edge to v\n INS[v].add(u)\n\n #1. Store all vertices with indegree 0 in a queue\n #We will start\n topvertices = collection_type()\n\n for v,in_vertices in INS.iteritems():\n if len(in_vertices) == 0:\n topvertices.add(v)\n\n result = []\n\n #4. Perform steps 2 and 3 while the queue is not empty.\n while len(topvertices) != 0: \n #2. get a vertex U and place it in the sorted sequence (array or another queue).\n u = topvertices.pop()\n result.append(u)\n\n #3. For all edges (U,V) update the indegree of V,\n # and put V in the queue if the updated indegree is 0.\n\n for v in OUTS[u]:\n INS[v].remove(u)\n if len(INS[v]) == 0:\n topvertices.add(v)\n\n return result\n\nclass stack_collection:\n def __init__(self):\n self.data = list()\n def add(self,v):\n self.data.append(v)\n def pop(self):\n return self.data.pop()\n def __len__(self):\n return len(self.data)\n\nclass queue_collection:\n def __init__(self):\n self.data = deque()\n def add(self,v):\n self.data.append(v)\n def pop(self):\n return self.data.popleft()\n def __len__(self):\n return len(self.data)\n\nclass random_orderd_collection:\n def __init__(self):\n self.data = []\n def add(self,v):\n self.data.append(v)\n def pop(self): \n result = random.choice(self.data)\n self.data.remove(result)\n return result\n def __len__(self):\n return len(self.data)\n\n"""\nPoor man\'s graph generator.\nRequires networkx.\n\nDon\'t make the edge_count too high compared with the vertex count,\n otherwise it will run for a long time or forever.\n"""\ndef nx_generate_random_dag(vertex_count,edge_count):\n import networkx as nx\n\n V = range(1,vertex_count+1)\n random.shuffle(V)\n\n G = nx.DiGraph()\n G.add_nodes_from(V)\n\n while nx.number_of_edges(G) < edge_count:\n\n u = random.choice(V)\n v = random.choice(V)\n if u == v:\n continue\n\n for tries in range(2):\n G.add_edge(u,v)\n if not nx.is_directed_acyclic_graph(G):\n G.remove_edge(u,v)\n u,v = v,u\n V = G.nodes()\n E = G.edges()\n\n assert len(E) == edge_count\n assert len(V) == vertex_count\n return V,E\n\n\n\n\ndef main():\n\n graphs = []\n\n V = [1,2,3,4,5]\n E = [(1,2),(1,5),(1,4),(2,4),(2,5),(3,4),(3,5)]\n\n graphs.append((V,E))\n\n """\n Uncomment this section if you have networkx.\n This will generate 3 random graphs.\n """\n """\n for i in range(3):\n G = nx_generate_random_dag(30,120)\n V,E = G\n print \'random E:\',E\n graphs.append(G)\n """\n\n\n #This graph was generated using nx_generate_random_dag() from above\n V = range(1,31)\n E = [(1, 10), (1, 11), (1, 14), (1, 17), (1, 18), (1, 21), (1, 23),\n (1, 30), (2, 4), (2, 12), (2, 15), (2, 17), (2, 18), (2, 19),\n (2, 25), (3, 22), (4, 5), (4, 8), (4, 22), (4, 23), (4, 26),\n (5, 27), (5, 23), (6, 24), (6, 28), (6, 27), (6, 20), (6, 29),\n (7, 3), (7, 19), (7, 13), (8, 24), (8, 10), (8, 3), (8, 12),\n (9, 4), (9, 8), (9, 10), (9, 14), (9, 19), (9, 27), (9, 28),\n (9, 29), (10, 18), (10, 5), (10, 23), (11, 27), (11, 5),\n (12, 10), (13, 9), (13, 26), (13, 3), (13, 12), (13, 6), (14, 24),\n (14, 28), (14, 18), (14, 20), (15, 3), (15, 12), (15, 17), (15, 19),\n (15, 25), (15, 27), (16, 4), (16, 5), (16, 8), (16, 18), (16, 20), (16, 23),\n (16, 26), (16, 28), (17, 4), (17, 5), (17, 8), (17, 12), (17, 22), (17, 28),\n (18, 11), (18, 3), (19, 10), (19, 18), (19, 5), (19, 22), (20, 5), (20, 29),\n (21, 25), (21, 12), (21, 30), (21, 17), (22, 11), (24, 3), (24, 10),\n (24, 11), (24, 28), (25, 10), (25, 17), (25, 23), (25, 27), (26, 3),\n (26, 18), (26, 19), (28, 26), (28, 11), (28, 23), (29, 2), (29, 4),\n (29, 11), (29, 15), (29, 17), (29, 22), (29, 23), (30, 3), (30, 7),\n (30, 17), (30, 20), (30, 25), (30, 26), (30, 28), (30, 29)]\n\n graphs.append((V,E))\n\n #add other graphs here for testing\n\n\n for G in graphs:\n V,E = G\n\n #sets in python are unordered but in practice their hashes usually order integers.\n top_set = topsort(V,E,set)\n\n top_stack = topsort(V,E,stack_collection)\n\n top_queue = topsort(V,E,queue_collection)\n\n random_results = []\n for i in range(0,10):\n random_results.append(topsort(V,E,random_orderd_collection))\n\n print\n print \'V: \', V\n print \'E: \', E\n print \'top_set ({0}): {1}\'.format(is_topsorted(V,E,top_set),top_set)\n print \'top_stack ({0}): {1}\'.format(is_topsorted(V,E,top_stack),top_stack)\n print \'top_queue ({0}): {1}\'.format(is_topsorted(V,E,top_queue),top_queue)\n\n for random_result in random_results:\n print \'random_result ({0}): {1}\'.format(is_topsorted(V,E,random_result),random_result)\n assert is_topsorted(V,E,random_result)\n\n assert is_topsorted(V,E,top_set)\n assert is_topsorted(V,E,top_stack)\n assert is_topsorted(V,E,top_queue)\n\n\n\nmain()\n