algorithm - BFS与拓扑排序的关系

Question

拓扑排序既可以使用 DFS(具有反转的边)也可以使用队列来完成。 BFS 也可以使用队列来完成。使用队列进行 BFS 时元素的存储和检索方式与使用队列进行拓扑排序时的元素存储和检索方式之间是否存在任何关系。澄清会有所帮助。谢谢。

Answer 1

不，不一定有任何关系。我假设您指的是 Kahn 来自 wikipedia/Topological_sorting#Algorithms 的算法，维基百科指出:

Note that, reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack.

因此，用于拓扑排序的“队列”实际上是“任何集合”结构，并且该集合中的顺序无关紧要；它可以是任何东西。另一方面，用于 BFS 的队列完全是关于顺序的；这样它就可以完成其 FIFO(先进先出)任务。更改此顺序将破坏 BFS 算法。

可能还有其他基于“队列”的拓扑排序算法，其中结构是队列很重要。如果您询问的是特定的此类算法，请加以说明。

编辑:感兴趣的算法被阐明为 Improved algorithm section ，这与 Kahn 的相同。

编辑:我已经编写了一些代码，根据 Improved algorithm section 实现拓扑排序。在您链接的页面中。我制作了它使用任意类型的集合作为排序函数的参数。然后我制作了几种类型的此类集合，包括堆栈、队列、随机弹出集合和 python 集(它是一个哈希集，因此不保证顺序)。

然后我制作一个图表，并在每个集合上测试排序算法。然后我使用拓扑排序维基百科上列出的定义测试每个结果:

.. 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.

― wikipedia

代码是用python写的，如下。结果是 here来自 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()