我有一个依赖关系图，其中一个节点需要满足前一个节点的两个副本。我想使用拓扑排序来获得评估顺序，但问题是拓扑排序忽略了平行/多边，而只是将其视为一个依赖项。我建模错了吗，还是我需要一个特定的拓扑排序来处理多重图？
最佳答案
它可以通过修改拓扑排序算法来完成。
原始算法存储没有传入边(S)的所有节点的集合，主要步骤是从 S 中取出一个节点，将其从 S 中删除，并从图中删除它的所有边并检查是否有其他节点没有传入边。
将其更改为:从 S 取一个节点，为每个邻居删除一个边实例，如果节点没有出边将其从 S 中删除，请检查是否有其他节点没有入边。
原码来自 Wikipedia :
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
改变算法:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
take a node n from S
add n to tail of L
for each neighbouring node m of n
remove ONE edge (m,n) from the graph
if m has no other incoming edges then
insert m into S
if n doesn't have outgoing edges
remove n from S
关于graph - 依赖多图 : Topological Sort and evaluation of graphs with duplicate edges，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18862142/