拓扑排序可以使用DFS（反向边）和队列进行。BFS也可以使用队列进行。在使用队列进行BFS和拓扑排序时，元素的存储和检索方式之间是否存在关系？希望能得到澄清。谢谢。
BFS和拓扑排序的关系
7
- motiur
2
《Java数据结构和算法分析（第三版）》第11.3章非常清楚地描述了这一点。 - Eric
相关帖子 - 使用BFS进行拓扑排序，拓扑搜索和广度优先搜索，以及使用BFS进行拓扑排序。 - RBT
2个回答
3
从源节点开始的BFS逐层遍历使得节点按照它们与源节点的距离的顺序出现，这也意味着父节点会先于它们在下一层的子节点出现。
这可能看起来像我们需要进行拓扑排序，然而请跟随我。上一个句子中的“下一层”是关键，因为如果一个节点及其子节点与源节点在同一层，则BFS不强制对它们进行遍历顺序，这意味着它可能在节点本身之前呈现其子节点，这将直接违反拓扑排序规则，而当我们想要进行拓扑排序时，顺序确实很重要。
尽管似乎BFS和拓扑排序之间存在关系，但它们之间的关系相对较弱。
这可能看起来像我们需要进行拓扑排序，然而请跟随我。上一个句子中的“下一层”是关键，因为如果一个节点及其子节点与源节点在同一层，则BFS不强制对它们进行遍历顺序，这意味着它可能在节点本身之前呈现其子节点，这将直接违反拓扑排序规则，而当我们想要进行拓扑排序时，顺序确实很重要。
尽管似乎BFS和拓扑排序之间存在关系，但它们之间的关系相对较弱。
- Sarath M
2
不是的，它们之间没有必然联系。我假设你正在参考维基百科上关于Kahn算法的Topological_sorting#Algorithms部分，维基百科上指出：
请注意，反映了排序结果的非唯一性，结构S可以简单地是一个集合、队列或栈。
因此，拓扑排序的“队列”实际上是“任何集合”结构，这个集合的顺序并不重要；它可以是任何东西。另一方面，BFS所使用的队列完全是关于顺序的；这样它就可以完成它的先进先出任务。改变这个顺序将破坏BFS算法。
可能存在其他基于“队列”的拓扑排序算法，其中结构为队列很重要。如果您询问特定的算法，请澄清一下。
编辑： 需要关注的算法已经在链接页面中的Improved algorithm section中进行了澄清，该算法与Kahn的算法相同。
编辑： 我编写了一些代码，按照您链接页面中的Improved algorithm section 实现了拓扑排序。我将它使用的集合类型作为排序函数的参数变量，然后创建了几种这样的集合类型，包括栈、队列、随机弹出集合和Python set（它是一个哈希集合，所以不能保证有序）。
然后我创建了一个图，并对每个集合测试了排序算法。然后我使用维基百科关于拓扑排序的定义测试了每个结果：
..定向图的一个拓扑排序是其顶点的线性排列，使得每条边uv中，u在排列中都出现在v的前面。
― 维基百科
代码是用Python编写的，并如下所示。结果可以在这里查看，来自http://ideone.com。我不知道一种好的易于生成测试用随机DAG的方法，所以我的测试图很弱。请随意评论/编辑一个好的DAG生成器。
编辑：现在我有一个不那么糟糕的生成器，但它使用了networkx。函数nx_generate_random_dag在代码中，但它在函数中导入了networkx。您可以取消main中标记部分的注释以生成图形。我在代码中硬编码了一个生成的图形，所以我们可以得到更有趣的结果。
所有这些都是为了表明，“集合”数据结构（算法中的队列）的排序可以是任何顺序。
from collections import deque
import random
def is_topsorted(V,E,sequence):
sequence = list(sequence)
#from wikipedia definition of top-sort
#for every edge uv, u comes before v in the ordering
for u,v in E:
ui = sequence.index(u)
vi = sequence.index(v)
if not (ui < vi):
return False
return True
#the collection_type should behave like a set:
# it must have add(), pop() and __len__() as members.
def topsort(V,E,collection_type):
#out edges
INS = {}
#in edges
OUTS = {}
for v in V:
INS[v] = set()
OUTS[v] = set()
#for each edge u,v,
for u,v in E:
#record the out-edge from u
OUTS[u].add(v)
#record the in-edge to v
INS[v].add(u)
#1. Store all vertices with indegree 0 in a queue
#We will start
topvertices = collection_type()
for v,in_vertices in INS.iteritems():
if len(in_vertices) == 0:
topvertices.add(v)
result = []
#4. Perform steps 2 and 3 while the queue is not empty.
while len(topvertices) != 0:
#2. get a vertex U and place it in the sorted sequence (array or another queue).
u = topvertices.pop()
result.append(u)
#3. For all edges (U,V) update the indegree of V,
# and put V in the queue if the updated indegree is 0.
for v in OUTS[u]:
INS[v].remove(u)
if len(INS[v]) == 0:
topvertices.add(v)
return result
class stack_collection:
def __init__(self):
self.data = list()
def add(self,v):
self.data.append(v)
def pop(self):
return self.data.pop()
def __len__(self):
return len(self.data)
class queue_collection:
def __init__(self):
self.data = deque()
def add(self,v):
self.data.append(v)
def pop(self):
return self.data.popleft()
def __len__(self):
return len(self.data)
class random_orderd_collection:
def __init__(self):
self.data = []
def add(self,v):
self.data.append(v)
def pop(self):
result = random.choice(self.data)
self.data.remove(result)
return result
def __len__(self):
return len(self.data)
"""
Poor man's graph generator.
Requires networkx.
Don't make the edge_count too high compared with the vertex count,
otherwise it will run for a long time or forever.
"""
def nx_generate_random_dag(vertex_count,edge_count):
import networkx as nx
V = range(1,vertex_count+1)
random.shuffle(V)
G = nx.DiGraph()
G.add_nodes_from(V)
while nx.number_of_edges(G) < edge_count:
u = random.choice(V)
v = random.choice(V)
if u == v:
continue
for tries in range(2):
G.add_edge(u,v)
if not nx.is_directed_acyclic_graph(G):
G.remove_edge(u,v)
u,v = v,u
V = G.nodes()
E = G.edges()
assert len(E) == edge_count
assert len(V) == vertex_count
return V,E
def main():
graphs = []
V = [1,2,3,4,5]
E = [(1,2),(1,5),(1,4),(2,4),(2,5),(3,4),(3,5)]
graphs.append((V,E))
"""
Uncomment this section if you have networkx.
This will generate 3 random graphs.
"""
"""
for i in range(3):
G = nx_generate_random_dag(30,120)
V,E = G
print 'random E:',E
graphs.append(G)
"""
#This graph was generated using nx_generate_random_dag() from above
V = range(1,31)
E = [(1, 10), (1, 11), (1, 14), (1, 17), (1, 18), (1, 21), (1, 23),
(1, 30), (2, 4), (2, 12), (2, 15), (2, 17), (2, 18), (2, 19),
(2, 25), (3, 22), (4, 5), (4, 8), (4, 22), (4, 23), (4, 26),
(5, 27), (5, 23), (6, 24), (6, 28), (6, 27), (6, 20), (6, 29),
(7, 3), (7, 19), (7, 13), (8, 24), (8, 10), (8, 3), (8, 12),
(9, 4), (9, 8), (9, 10), (9, 14), (9, 19), (9, 27), (9, 28),
(9, 29), (10, 18), (10, 5), (10, 23), (11, 27), (11, 5),
(12, 10), (13, 9), (13, 26), (13, 3), (13, 12), (13, 6), (14, 24),
(14, 28), (14, 18), (14, 20), (15, 3), (15, 12), (15, 17), (15, 19),
(15, 25), (15, 27), (16, 4), (16, 5), (16, 8), (16, 18), (16, 20), (16, 23),
(16, 26), (16, 28), (17, 4), (17, 5), (17, 8), (17, 12), (17, 22), (17, 28),
(18, 11), (18, 3), (19, 10), (19, 18), (19, 5), (19, 22), (20, 5), (20, 29),
(21, 25), (21, 12), (21, 30), (21, 17), (22, 11), (24, 3), (24, 10),
(24, 11), (24, 28), (25, 10), (25, 17), (25, 23), (25, 27), (26, 3),
(26, 18), (26, 19), (28, 26), (28, 11), (28, 23), (29, 2), (29, 4),
(29, 11), (29, 15), (29, 17), (29, 22), (29, 23), (30, 3), (30, 7),
(30, 17), (30, 20), (30, 25), (30, 26), (30, 28), (30, 29)]
graphs.append((V,E))
#add other graphs here for testing
for G in graphs:
V,E = G
#sets in python are unordered but in practice their hashes usually order integers.
top_set = topsort(V,E,set)
top_stack = topsort(V,E,stack_collection)
top_queue = topsort(V,E,queue_collection)
random_results = []
for i in range(0,10):
random_results.append(topsort(V,E,random_orderd_collection))
print
print 'V: ', V
print 'E: ', E
print 'top_set ({0}): {1}'.format(is_topsorted(V,E,top_set),top_set)
print 'top_stack ({0}): {1}'.format(is_topsorted(V,E,top_stack),top_stack)
print 'top_queue ({0}): {1}'.format(is_topsorted(V,E,top_queue),top_queue)
for random_result in random_results:
print 'random_result ({0}): {1}'.format(is_topsorted(V,E,random_result),random_result)
assert is_topsorted(V,E,random_result)
assert is_topsorted(V,E,top_set)
assert is_topsorted(V,E,top_stack)
assert is_topsorted(V,E,top_queue)
main()
- Realz Slaw
6
1有一个关于使用队列执行拓扑排序的描述。使用入度和出度的概念类似于BFS（广度优先搜索）中逐层遍历的概念。顺便说一句：我认为你上面提到的应该是BFS而不是DFS。http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L20-TopSort.htm - motiur
第四部分。改进的算法与Kahn描述的完全相同。将所有入度为0的顶点存储在队列中，这个结构的排序并不重要。数组或另一个队列的排序很重要，但这只是排序的结果，所以我确定这不是你想要的队列。 - Realz Slaw
1是的，我专注于顶点具有相同入度的事实，首先它们的子节点被处理（类似于BFS中的第二级），然后父节点被处理（类似于BFS中的第一级）；然后再按照FIFO的概念处理父节点。这听起来不是和BFS算法很相似吗？ - motiur
它们之间存在相似性；BFS和这个算法都是按“层级”遍历图形。然而，BFS关心层级内的顺序，而拓扑排序则不关心。顺便说一句：我认为BFS在实际的DAG上可能效果不太好，因为可能会有多个“根”。好问题，这有助于澄清。 - Realz Slaw
"BFS关心层内的顺序。拓扑排序则不关心。" 你能给出一个好的引用来证明这个事实吗？此外，我认为，我同意拓扑排序存在多个根节点的问题；而BFS通常只有一个根节点。 - motiur
让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/16610/discussion-between-motiur-rahman-and-realz-slaw - motiur
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接