如何代表与替代路径的依赖关系图

Question

我有一些麻烦，试图代表和在这种情况下操作的依赖关系图：

• 节点有一定的依赖关系必须解决
• 每一条路径不能有依赖性的for循环（如在DAG图）
• 每个依赖可以由一个以上的其他节点

我从目标节点开始，递归地寻找可以解决其依赖关系，但必须维护上述属性，尤其是第三个属性。

只是一个小例子这里：

我想有类似以下

  (A) 
     / \ 
     / \ 
     /  \ 
    [(B),(C),(D)] (E) 
    /\  \ 
/\  (H) 
(F) (G) 

这意味着图：

• F，G，C，H，E没有相关性
• D依赖于H
• B取决于F和G
• A依赖E上和
  • 乙或
  • Ç或
  • d

所以，如果我写下所有可能的拓扑排序的路径到AI应该有：

1. ë - >的F - “G - >乙 - >甲
2. ë - ”ç - >甲
3. ë - >ħ - > d - >甲

如何可以建模带有这些属性的图表？哪种数据结构更适合这样做？

Answer 1

您应该使用一个正常的邻接列表和一个附加属性，其中一个节点知道其他节点也会满足相同的依赖关系。这意味着B，C，D应该都知道它们属于同一个等价类。你可以通过将它们全部插入到一个集合中来实现。

Node: 
    List<Node> adjacencyList 
    Set<Node> equivalentDependencies 

要在拓扑排序使用此数据结构，当你删除一个源，并删除其所有的出边，也删除其等价类中的节点，它们的出边，并递归删除节点那指向他们。 维基百科：

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 o in the equivalency class of n <===removing equivalent dependencies 
     remove j from S 
      for each node k with an edge e from j to k do 
       remove edge e from the graph 
       if k has no other incoming edges then 
        insert k into S  
    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 
if graph has edges then 
    return error (graph has at least one cycle) 
else 
    return L (a topologically sorted order) 

该算法会给你修改topologicaly排序的路径之一。