将有向图按拓扑排序到不相交的子图的存储桶中 [英] Topologically sort directed graph into buckets for disjoint sub graphs
本文介绍了将有向图按拓扑排序到不相交的子图的存储桶中的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在寻找一种算法,该算法可以对图形进行拓扑排序,从而生成一组列表,每个列表包含不相交子图的拓扑排序顶点.
I am looking for an algorithm which can take a graph and topologically sort it such that it produces a set of lists, each which contains the topologically sorted vertices of a disjoint subgraph.
当节点依赖两个不同列表中的节点时,困难的部分是合并列表.
The difficult part is merging the lists when a node depends on a node in two different lists.
这是我不完整的代码/伪代码,其中graph是字典 {node:[node,node,...]}}
Here is my incomplete code/pseudocode where graph is a dict {node: [node, node, ...]}
sorted_subgraphs = []
while graph:
cyclic = True
for node, edges in list(graph.items()):
for edge in edges:
if edge in graph:
break
else:
del graph[node]
cyclic = False
sub_sorted = []
for edge in edges:
bucket.extend(...) # Get the list with edge in it, and remove it from sorted_subgraphs
bucket.append(node)
sorted_subgraphs.append(bucket)
if cyclic:
raise Exception('Cyclic graph')
推荐答案
首先使用泛洪填充算法将其划分为不相交的子图,然后对每个图进行拓扑排序.
First divide it into disjoint subgraphs using a flood fill algorithm, and then topologically sort each one.
这篇关于将有向图按拓扑排序到不相交的子图的存储桶中的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文