Representing a minimum spanning tree using an adjacency list

Question

I have been attempting to solve a problem for class. The problem is:

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

In order to pass this question my function must take in, and return, an adjacency list. However, I'm not sure how to go about representing the input and output as an adjacency list.

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

Let's say that you compute the minimum spanning tree as the list of edges called MST. Now, MST contains triples (u, v, weight). What you can do is to iterate over edges in MST and for each such edge (u, v, weight) append a tuple (v, weight) to the adjacency list of u, and also append a tuple (u, weight) to the adjacency list of v. In pseudo-code it may look like that:

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