如何代表與替代路徑的依賴關係圖

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排序的路徑之一。