http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
Like Kruskal’s algorithm, Prim’s algorithm is also a Greedy algorithm.
It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
A group of edges that connects two set of vertices in a graph is called cut in graph theory. So, at every step of Prim’s algorithm, we find a cut (of two sets, one contains the vertices already included in MST and other contains rest of the verices), pick the minimum weight edge from the cut and include this vertex to MST Set (the set that contains already included vertices).
How does Prim’s Algorithm Work? The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
Algorithm
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
….a) Pick a vertex u which is not there in mstSet and has minimum key value.
….b) Include u to mstSet.
….c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v
Java Implementation
http://algs4.cs.princeton.edu/43mst/PrimMST.java.html
http://algs4.cs.princeton.edu/43mst/LazyPrimMST.java.html
http://www.sanfoundry.com/java-program-find-mst-using-prims-algorithm/
Read full article from Greedy Algorithms | Set 5 (Prim’s Minimum Spanning Tree (MST)) | GeeksforGeeks
Like Kruskal’s algorithm, Prim’s algorithm is also a Greedy algorithm.
It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
A group of edges that connects two set of vertices in a graph is called cut in graph theory. So, at every step of Prim’s algorithm, we find a cut (of two sets, one contains the vertices already included in MST and other contains rest of the verices), pick the minimum weight edge from the cut and include this vertex to MST Set (the set that contains already included vertices).
How does Prim’s Algorithm Work? The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
Algorithm
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
….a) Pick a vertex u which is not there in mstSet and has minimum key value.
….b) Include u to mstSet.
….c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v
Also read http://algs4.cs.princeton.edu/43mst/// A utility function to find the vertex with minimum key value, from
// the set of vertices not yet included in MST
int
minKey(
int
key[],
bool
mstSet[])
{
// Initialize min value
int
min = INT_MAX, min_index;
for
(
int
v = 0; v < V; v++)
if
(mstSet[v] ==
false
&& key[v] < min)
min = key[v], min_index = v;
return
min_index;
}
// A utility function to print the constructed MST stored in parent[]
int
printMST(
int
parent[],
int
n,
int
graph[V][V])
{
printf
(
"Edge Weight\n"
);
for
(
int
i = 1; i < V; i++)
printf
(
"%d - %d %d \n"
, parent[i], i, graph[i][parent[i]]);
}
// Function to construct and print MST for a graph represented using adjacency
// matrix representation
void
primMST(
int
graph[V][V])
{
int
parent[V];
// Array to store constructed MST
int
key[V];
// Key values used to pick minimum weight edge in cut
bool
mstSet[V];
// To represent set of vertices not yet included in MST
// Initialize all keys as INFINITE
for
(
int
i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] =
false
;
// Always include first 1st vertex in MST.
key[0] = 0;
// Make key 0 so that this vertex is picked as first vertex
parent[0] = -1;
// First node is always root of MST
// The MST will have V vertices
for
(
int
count = 0; count < V-1; count++)
{
// Pick thd minimum key vertex from the set of vertices
// not yet included in MST
int
u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] =
true
;
// Update key value and parent index of the adjacent vertices of
// the picked vertex. Consider only those vertices which are not yet
// included in MST
for
(
int
v = 0; v < V; v++)
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if
(graph[u][v] && mstSet[v] ==
false
&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// print the constructed MST
printMST(parent, V, graph);
}
Java Implementation
http://algs4.cs.princeton.edu/43mst/PrimMST.java.html
http://algs4.cs.princeton.edu/43mst/LazyPrimMST.java.html
http://www.sanfoundry.com/java-program-find-mst-using-prims-algorithm/
Read full article from Greedy Algorithms | Set 5 (Prim’s Minimum Spanning Tree (MST)) | GeeksforGeeks