使用邻接表表示最小生成树

Question

我一直在尝试解决 class 的问题。问题是：

Given an undirected graph G, find the minimum spanning tree within G.

为了通过这个问题，我的函数必须接受 return 一个 邻接列表 。但是，我不确定如何将输入和输出表示为邻接列表。

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))

使用邻接表表示最小生成树

Representing a minimum spanning tree using an adjacency list

python

algorithm

graph

minimum-spanning-tree

kruskals-algorithm