兩個網絡圖的聯合

Question

任何人都可以指出正確的數據結構/算法來完成以下任務嗎？

我想結合（Union？）下面兩組節點來獲得第三組。

謝謝！

Answer 1

簡答題

1. 聯合節點集。
2. 聯合邊集。

龍答案

我假設你正在使用的圖形數據結構，其中有Node情況，其中每個Node有string Name和list<Node> Next。

我們打電話給你的兩張圖G和H，其中圖是list<Node>。

令GNames和HNames是每個圖中節點名稱的集合。假設MNames是GNames和HNames的聯合。

創建一個新圖list<Node> M其中有一個新的Node爲MNames中的每個名稱。

構建map<string, Node> GLookup, HLookup, MLookup作爲從節點名到Node的映射，對於list<Node> G, H, M中的每一個。

對於這個新圖M每個Node u，在NextNames計算NextNames爲GLookup[u.Name].Next.Select(v => v.Name)和HLookup[u.Name].Next.Select(v => v.Name)工會，然後爲每個名字name，加MLookup[name]到u.Next。

M現在是您的合併圖。

僞

list<Node> merge(list<Node> G, list<Node> H) 
    GNames = G.Select(u => u.Name) 
    HNames = H.Select(u => u.Name) 
    MNames = union(GNames, HNames) 
    M = MNames.Select(name => new Node(name)) 
    GLookup = G.ToMap(u => u.Name) 
    HLookup = H.ToMap(u => u.Name) 
    MLookup = M.ToMap(u => u.Name) 
    foreach u in M 
     NextNames = union(
         GLookup[u.Name].Next.Select(v => v.Name), 
         HLookup[u.Name].Next.Select(v => v.Name)) 
     foreach name in NextNames 
      u.Next.Add(MLookup[name]) 
    return M 

Answer 2

通常圖形可以表示爲任一鄰接矩陣或鄰接列表。無論哪種方式聯合他們並不難。

從鄰接表的角度來看，你有

list1 = [[A,[B,K]],[B,[C,D,E]],...] 
list2 = [[A,[B]],[B,[C,D,E]],...] 

因此，所有你必須做的就是工會在鄰接表

list3 = [[A,UNION([B,K],[B])]...] 

對於鄰接矩陣每個節點的子列表，它是不重要的。簡單地通過矩陣中的每個的aij循環，並且如果它是0，並且在另一矩陣中的對應條目是1，則設置爲1。

如果圖1具有類似：

A B C 
A 1 1 0 
B 0 1 0 
C 0 1 1 

和圖形2有這樣的事情：

A B C 
A 1 1 0 
B 0 1 1 
C 0 0 1 

然後圖3最終會

A B C 
A 1 1 0 
B 0 1 1 
C 0 1 1