Lab 6 – MST

A spanning tree of a given connected undirected graph is a subgraph that connects all the vertices. One graph may have several different spanning trees. For a weighted graph, the weight of its spanning tree is the sum of the weights of its edges.

A Minimum Spanning Tree (MST) is a spanning tree with the weight less or equal to the weights of any other spanning tree.

There are two commonly used algorithms for finding the MST of a given graph: Prim’s algorithm and Kruskal’s algorithm.

Assignment: Fing the MST of a given graph using Prim’s algorithm.

Input:

• a connected, weighted, undirected graph
• a number from 1 to N (N= number of vertices) representing the starting vertex

Output:

• the MST
• the weight of the MST

Due to: January 23rd

Prim(G, w, s)
FOREACH (v in V)
p[v] = NULL; d[v] = INF; d[s] = 0
A = emptySet(); S = emptySet();
Q = PRIORITY-QUEUE(V, d)
WHILE (!Q.EMPTY())
u = Q.EXTRACT-MIN()
S = S U {u};
A = A U {(u, p[u])}
FOREACH (v, Adj[u])
IF (d[v] >w(u,v))
d[v] = w(u,v)
p[v] = u
RETURN A \{(s, p(s))}

Demo here.