使用鄰接表來表示最小生成樹

Question

我一直在試圖解決類的問題。問題是：

給定一個無向圖摹，發現摹內的最小生成樹。

爲了通過這個問題，我的函數必須採取，並返回，一鄰接表。但是，我不確定如何去將輸入和輸出表示爲鄰接列表。

from collections import defaultdict 

class Graph: 

    def __init__(self,vertices): 
     self.V= vertices 
     self.graph = [] 

    def Edge(self,u,v,w): 
     self.graph.append([u,v,w]) 

    # A utility function to find set of an element i 
    def find(self, parent, i): 
     if parent[i] == i: 
      return i 
     return self.find(parent, parent[i]) 

    # A function that does union of two sets of x and y 
    def union(self, parent, rank, x, y): 
     xroot = self.find(parent, x) 
     yroot = self.find(parent, y) 

     # Attach smaller rank tree under root of high rank tree 
     if rank[xroot] < rank[yroot]: 
      parent[xroot] = yroot 
     elif rank[xroot] > rank[yroot]: 
      parent[yroot] = xroot 
     # If ranks are same, then make one as root and increment rank by one 
     else : 
      parent[yroot] = xroot 
      rank[xroot] += 1 

    # The main function to build the MST 
    def Question3(G): 

     MST =[] # This will store the MST 
     e = 0 # An index variable used for MST[] 
     i = 0 # An index variable for sorted edges 
     G.graph = sorted(G.graph,key=lambda item: item[2]) 

     parent = [] ; rank = [] 

     # Create V subsets with single elements 
     for node in range(G.V): 
      parent.append(node) 
      rank.append(0) 

     # Edges to be taken is equal to V-1 
     while e < G.V -1 : 

      # Take smallest edge and increment the index 
      u,v,w = G.graph[i] 
      i = i + 1 
      x = G.find(parent, u) 
      y = G.find(parent ,v) 

      # If including this edge does't cause cycle, include it 
      # in result and increment the index of result for next edge 
      if x != y: 
       e = e + 1 
       MST.append([u,v,w]) 
       G.union(parent, rank, x, y) 
      # Else discard the edge 
     print "Minimum Spanning Tree" 
     for u,v,weight in MST: 
      print ("%d -- %d == %d" % (u,v,weight)) 

g = Graph(4) 
g.Edge(0, 1, 9) 
g.Edge(0, 2, 6) 
g.Edge(0, 3, 5) 
g.Edge(1, 3, 12) 
g.Edge(2, 3, 4) 
g.Question3() 
print """---End Question 3--- 
""" 

Answer 1

假設您將最小生成樹計算爲稱爲MST的邊的列表。現在，MST包含三元組(u, v, weight)。你可以做的是迭代MST中的邊，並且對於每個這樣的邊(u, v, weight)將元組(v, weight)附加到u的鄰接列表，並且還將元組(u, weight)附加到v的鄰接列表。在僞代碼中，它可能如下所示：

adj = {} # your resulting adjacency lists, one for each vertex in the graph 
for u, v, weight in MST: 
    if u not in adj: 
     adj[u] = [] 
    adj[u].append((v, weight)) 
    if v not in adj: 
     adj[v] = [] 
    adj[v].append((u, weight))