Prim's algorithm is a greedy algorithm which is used to find the minimum spanning tree of the connected graph.
What is minimum spanning tree?
Minimum spanning tree is a connected sub graph which includes all vertices in the graph together without any cycles at minimum cost.
Input Graph:
See Also:
C Program To Implement Dijkstra's Algorithm
C Program To Find Minimum Spanning Tree Using Prim's Algorithm
C Program To Find Minimum Spanning Tree Using Kruskal's Algorithm
C Program To Implement Breath First Search
C Program To Implement Depth First Search
What is minimum spanning tree?
Minimum spanning tree is a connected sub graph which includes all vertices in the graph together without any cycles at minimum cost.
1 6
+---------------------- V1 ----------------------+
| |
| 7 3 |
V2 --------------------+ +-----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
5 8
Step 1: Select the start vertex V1.
1 6
+---------------------- V1 ----------------------+
| |
| 7 3 |
V2 --------------------+ +-----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
5 8
Step 2: Find the unvisited edges connected to V1 and select the edge with minimum cost. Edge V1-V2 is selected since it has the minimum cost.
1 6
+---------------------- V1 ----------------------+
| |
| 7 3 |
V2 --------------------+ +-----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
5 8
Step 3: Find the unvisited edges connected to V2 and select the edge with minimum cost. Edge V2-V4 is selected since it has the minimum cost.
1 6
+---------------------- V1 ----------------------+
| |
| 7 3 |
V2 --------------------+ +-----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
5 8
Step 4: Find the unvisited edges connected to V4 and select the edge with minimum cost. Edge V4-V6 is selected since it has the minimum cost.
1 6
+---------------------- V1 ----------------------+
| |
| 7 3 |
V2 --------------------+ +-----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
5 8
Step 5: Find the unvisited edges connected to V6 and select the edge with minimum cost. Edge V6-V3 is selected since it has the minimum cost.
1 6
+---------------------- V1 ----------------------+
| |
| 7 3 |
V2 --------------------+ +-----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
5 8
Step 6: Find the unvisited edges connected to V3 and select the edge with minimum cost. Edge V3-V5 is selected since it has the minimum cost.
1 6
+---------------------- V1 ----------------------+
| |
| 7 3 |
V2 --------------------+ +-----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
5 8
Resultant Minimum Spanning Tree:
1
+---------------------- V1
|
| 3
V2 +-----------------------V3
| | |
2 | | | 4
V4 | V5
| |
| |
+---------------------- V6
5
Cost of the given Minimum Spanning Tree is 15.
See Also:
C Program To Implement Dijkstra's Algorithm
C Program To Find Minimum Spanning Tree Using Prim's Algorithm
C Program To Find Minimum Spanning Tree Using Kruskal's Algorithm
C Program To Implement Breath First Search
C Program To Implement Depth First Search
Example Program To Implement Minimum Spanning Tree Using Prim's Algorithm:
#include <stdlib.h>
#define MAXVERTICES 1000
#define INFINITY 99999
struct vertex {
int visited, predecessor;
int dist;
};
int treeEdge[MAXVERTICES][2], mstCost;
int graphEdge[MAXVERTICES][MAXVERTICES], nodeCount;
struct vertex node[MAXVERTICES];
/* construct the input graph */
void buildGraph() {
int i = 1, source, dest, weight;
printf("Enter the no of vertices:");
scanf("%d", &nodeCount);
while (i <= (nodeCount * (nodeCount - 1) / 2)) {
printf("Edge(x to y)/(x<->x to exit):");
scanf("%d%d", &source, &dest);
if (source == dest)
break;
if (source > nodeCount || dest > nodeCount ||
source <= 0 || dest <= 0) {
printf("Not a valid edge!!\n");
continue;
} else {
printf("Weight for the edge %d to %d:", source, dest);
scanf("%d", &weight);
/* update weight of the edge */
graphEdge[source][dest] = weight;
graphEdge[dest][source] = weight;
}
i++;
}
if (i < nodeCount - 1) {
printf("Unable to build Minimum Spanning Tree\n");
exit(0);
}
return;
}
/* all vertices are visited or not */
int allVisited() {
int i;
for (i = 1; i <= nodeCount; i++)
if (node[i].visited == 0)
return 0;
return 1;
}
/* construct minimum spanning tree */
int buildTree() {
int i = 1, currentNode, count = 0, mindist;
while (i <= nodeCount) {
node[i].visited = 0;
node[i].predecessor = 0;
node[i].dist = INFINITY;
i++;
}
node[1].visited = 1;
node[1].dist = 0;
currentNode = 1;
while (allVisited() == 0) {
for (i = 1; i <= nodeCount; i++) {
/* Find the adjacent vertices and update the edge lenght */
if(graphEdge[currentNode][i] > 0 && node[i].visited == 0) {
if (graphEdge[currentNode][i] < node[i].dist) {
node[i].predecessor = currentNode;
node[i].dist = graphEdge[currentNode][i];
}
}
}
mindist = INFINITY;
/* find the edge with minimum legth */
for (i = 1; i <= nodeCount; i++) {
if (node[i].dist < mindist && node[i].visited == 0) {
mindist = node[i].dist;
currentNode = i;
}
}
/* Mark the vertex as visited - edge with min cost */
node[currentNode].visited = 1;
count++;
treeEdge[count][0] = node[currentNode].predecessor;
treeEdge[count][1] = currentNode;
/* calculate cost of MST */
mstCost = mstCost + graphEdge[treeEdge[count][0]][treeEdge[count][1]];
}
return count;
}
int main() {
int i, count;
/* construct graph */
buildGraph();
count = buildTree();
printf("MST is composed of below edges:\n");
for (i = 1; i <= count; i++) {
printf("%d<->%d\n", treeEdge[i][0], treeEdge[i][1]);
}
printf("\n");
printf("Cost of Minimum Spanning Tree: %d\n", mstCost);
return 0;
}
Output: (C Program To Implement MST Using Prim's Algorithm)
jp@jp-VirtualBox:~/$ ./a.out
Enter the no of vertices:6
Edge(x to y)/(x<->x to exit):1 2
Weight for the edge 1 to 2:1
Edge(x to y)/(x<->x to exit):2 4
Weight for the edge 2 to 4:2
Edge(x to y)/(x<->x to exit):2 6
Weight for the edge 2 to 6:7
Edge(x to y)/(x<->x to exit):4 6
Weight for the edge 4 to 6:5
Edge(x to y)/(x<->x to exit):1 3
Weight for the edge 1 to 3:6
Edge(x to y)/(x<->x to exit):3 6
Weight for the edge 3 to 6:3
Edge(x to y)/(x<->x to exit):3 5
Weight for the edge 3 to 5:4
Edge(x to y)/(x<->x to exit):5 6
Weight for the edge 5 to 6:8
Edge(x to y)/(x<->x to exit):0 0
MST is composed of below edges:
1<->2
2<->4
4<->6
6<->3
3<->5
Cost of Minimum Spanning Tree: 15
Enter the no of vertices:6
Edge(x to y)/(x<->x to exit):1 2
Weight for the edge 1 to 2:1
Edge(x to y)/(x<->x to exit):2 4
Weight for the edge 2 to 4:2
Edge(x to y)/(x<->x to exit):2 6
Weight for the edge 2 to 6:7
Edge(x to y)/(x<->x to exit):4 6
Weight for the edge 4 to 6:5
Edge(x to y)/(x<->x to exit):1 3
Weight for the edge 1 to 3:6
Edge(x to y)/(x<->x to exit):3 6
Weight for the edge 3 to 6:3
Edge(x to y)/(x<->x to exit):3 5
Weight for the edge 3 to 5:4
Edge(x to y)/(x<->x to exit):5 6
Weight for the edge 5 to 6:8
Edge(x to y)/(x<->x to exit):0 0
MST is composed of below edges:
1<->2
2<->4
4<->6
6<->3
3<->5
Cost of Minimum Spanning Tree: 15
excellently worked, can this program any be reduced further,because my professor wont believe me if i did this long program and executed by myself... u feel me right.
ReplyDeleteVery Useful Post!Thanks!
ReplyDeleteData Structure Programming - Prim’s Algorithm