BFS与拓扑分类之间的关系 [英] Relationship between BFS and topological sort
问题描述
可以使用DFS（具有相反的边）并使用队列来完成拓扑排序。也可以使用队列完成BFS。在使用队列进行拓扑排序时，在使用BFS的队列时，元素的存储和检索方式之间存在任何关系。澄清将会有所帮助。谢谢。
不，没有任何关系。我假设你是指从Kahn算法的维基百科/拓扑调整算法，维基百科注意：
注意，反映结果排序的非唯一性，结构S可以简单地是一个集合或一个队列或堆栈。
因此，用于拓扑排序的队列实际上是任何集合结构，并且此集合中的排序并不重要;它可以是任何东西。另一方面，用于BFS的队列是关于订单的;以便它可以完成其FIFO（先进先出）任务。更改此排序将会破坏BFS算法。
可能还有其他基于队列的拓扑排序算法，其中结构是队列的重要性。如果您询问特定的算法，请澄清。
编辑：感兴趣的算法被澄清为改进的算法部分，与Kahn的相同。 p>
编辑：我已经编写了一些根据改进的算法部分在您链接的页面。我将其使用的任意类型作为排序函数的参数。然后，我做一些类型的这样的集合，包括一个堆栈，一个队列，一个随机弹出集合和一个python集合（它的一个哈希集，所以没有保证订单）。
然后我做一个图表，并对每个集合的排序算法进行测试。然后我使用拓扑排序维基百科列出的定义来测试每个结果：
..拓扑排序（有时缩写为topsort或toposort ）或有向图的拓扑排序是其顶点的线性排序，使得对于每个边uv，u在顺序中都在v之前。
- 维基百科
代码是用python编写的，并遵循。结果是 http的此处 ：//ideone.com 。我不知道一个很好的方法来生成随机DAG进行测试，所以我的测试图是跛脚的。请自行评论/编辑好的DAG生成器。
编辑：现在我有一个较少的跛脚生成器，但它使用networkx。函数 nx_generate_random_dag 在代码中，但是在函数中导入了networkx。您可以取消注释main中标记的部分来生成图形。我将生成的图形硬编码到代码中，所以我们得到更多有趣的结果。
所有这一切都是为了表明收集数据结构的顺序算法中的队列）可以是任何顺序的。
从集合导入deque
import random
def is_topsorted（V ，E，序列）：
序列=列表（序列）
＃从维基百科定义顶级排序
＃为每个边缘uv，u在订单
之前v u，v in E：
ui = sequence.index（u）
vi = sequence.index（v）
如果不是（ui< vi）：
return False
return True
#the collection_type应该像一个集合：
＃它必须有add（），pop（）和__len __（）作为成员。
def topsort（V，E，collection_type）：
#out边缘
INS = {}
#in边
OUTS = {}
for v in V：
INS [v] = set（）
OUTS [v] = set（）
＃为每个边u，v，
for u，v in E：
#record从u
的外边缘OUTS [u] .add（v）
#record的边缘到v
INS [v] .add（u）
＃1。将所有具有不等式0的顶点存储在队列中
#We将启动
topvertices = collection_type（）
for v，in_vertices in INS.iteritems（）：
if len（in_vertices）== 0：
topvertices.add（v）
result = []
＃4。队列不为空时执行步骤2和3。
while len（topvertices）！= 0：
＃2。获取顶点U并将其放在排序顺序（数组或另一个队列）中。
u = topvertices.pop（）
result.append（u）
＃3。对于所有边缘（U，V），如果更新的indegree为0，则更新V，v b $ b＃的不等式，并将V置于队列中。
for OU in OUTS [u]：
INS [v] .remove（u）
如果len（INS [v]）== 0：
topvertices.add（v）
返回结果
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）
可怜的人的图形生成器。
需要networkx。
不要使edge_count与顶点数相比太高，
否则会运行很长时间或永远。
def nx_generate_random_dag（vertex_count，edge_count）：
导入networkx为nx
V =范围（1，vertex_count + 1）
随机.shuffle（V）
G = nx.DiGraph（）
G.add_nodes_from（V）
而nx.number_of_edges（G）< edge_count：
u = random.choice（V）
v = random.choice（V）
如果u == v：
continue
用于尝试在范围（2）：
G.add_edge（u，v）
如果不是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））
如果您有networkx，请取消注释本节。
这将生成3个随机图。
for i in range（3）：
G = nx_generate_random_dag（30,120）
V，E = G
print 'random E：'，E
graphs.append（G）
＃这个图是使用nx_generate_random_dag（）从
V =范围（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），（4，23），（4,26），（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,8），（9,10），（9,14），（9,19），（9,27），（9,28），
（9,29）， ，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，5），（17,8），（17,12），（17,22），（17,28），
（18,11），（18,3） （20，29），（19，18），（19，5），（19,22），（20，5），（20，29），
（21,25） ，（21，30），（21，17），（22，11），（24，3），（24，10），
（24，11），（24,28） （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） ，（30,27），（30,3），（30,7），
（30,17），（30,20），（30,25），（30,26） 28），（30,29）]
graphs.append（（V，E））
＃add其他图形用于测试
在图形中：
V，E = G
python中的#sets是无序的，但在实践中，它们的散列通常排序整数。
top_set = topsort（V，E，set）
top_stack = topsort（V，E，stack_collection）
top_queue = topsort（V，E，queue_collection）
random_results = []
在范围（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）
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）
在random_results中的random_result：
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（）
Topological sort can be done using both a DFS(having edges reversed) and also using a queue . A BFS can also be done using a queue . Is there any relationship between the way elements are stored and retrieved while using queue for a BFS to that when used a queue for topological sorting . Clarification will be helpful . Thanks.
No, there is not necessarily any relationship. I assume you are referring to the algorithm by Kahn from wikipedia/Topological_sorting#Algorithms, which wikipedia notes:
Note that, reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack.
Thus the "queue" for topological sorting is really "any collection" structure and the ordering in this collection does not matter; it can be anything. The queue used for BFS on the other hand, is all about the order; so that it can accomplish its FIFO (first-in, first-out) task. Changing this ordering will ruin the BFS algorithm.
There might be other "queue" based algorithms for topological sort, where it does matter that the structure is a queue. If you are asking about a particular such algorithm, please clarify.
EDIT: Algorithm of interest is clarified to be Improved algorithm section, which is the same as Kahn's.
EDIT: I've written some code that implements topological sort according to the Improved algorithm section in the page you linked. I made the type of collection it uses arbitrary as an argument of the sort function. I then make a few types of such collections, including a stack, a queue, a random-pop-collection and a python set (its a hashset, so no guarantees on order).
I then make a graph, and test the sorting algorithm on it with each collection. Then I test each of the results using the definition listed on wikipedia of topological sort:
.. a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering.
The code is written in python and follows. The result is here from http://ideone.com. I don't know a good easy way to generate random DAGs for testing so my test graph is lame. Feel free to comment/edit a good DAG generator.
EDIT: Now I have a less lame generator, but it uses networkx. The function nx_generate_random_dag is in the code, but it imports networkx in the function. You can uncomment the marked section in main to generate graphs. I hardcoded a generated graph into the code, so we get more interesting results.
All of this is to show, that the ordering of the "collection" data structure (the queue in the algorithm) can be in any order.
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()
这篇关于BFS与拓扑分类之间的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
