What is a tree?
A tree is nothing but a connected sub graph with no cycles.
Example:
V1------------V2
| |
V3------------V4
Above is an example for a graph and it has cycles(loop) in it. Lets us derive tree from the above graph.
Below is the tree derived from the given input graph and it has no cycles in it.
Trees:
V1------------V2
|
V3------------V4
V3
/ \
V1 V4
\
V2
What is minimum spanning tree?
Minimum spanning tree is a connected sub graph which includes all vertices of the graph together with minimum cost and there should not any cycles.
Construct Minimum Spanning Tree Using Kruskal's Algorithm:
Kruskal's algorithm uses greedy technique to find the minimum spanning tree for a connected weighted graph.
Input Graph:
1 3
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
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
A tree is nothing but a connected sub graph with no cycles.
Example:
V1------------V2
| |
V3------------V4
Above is an example for a graph and it has cycles(loop) in it. Lets us derive tree from the above graph.
Below is the tree derived from the given input graph and it has no cycles in it.
Trees:
V1------------V2
|
V3------------V4
V3
/ \
V1 V4
\
V2
What is minimum spanning tree?
Minimum spanning tree is a connected sub graph which includes all vertices of the graph together with minimum cost and there should not any cycles.
Construct Minimum Spanning Tree Using Kruskal's Algorithm:
Kruskal's algorithm uses greedy technique to find the minimum spanning tree for a connected weighted graph.
Input Graph:
1 3
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
Step 1: Select the edge with smallest length. Edge between V1 and V2 is selected.
1 3
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
Step 2: Find the next smallest edge and select it. Edge between V2 and V4 is selected.
1 3
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
Step 3: Select the next smallest edge. The edge between V1 and V3 is selected.
1 3
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
Step 4: The next smallest edge is present between V3 and V5.
1 3
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
Step 5: The next smallest edge is present between V2 and V6.
1 3
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
+--------------------- V1 -----------------------+
| |
| 5 6 |
V2 --------------------+ +----------------------V3
| | | |
2 | | | | 4
V4 | | V5
| | | |
| | | |
+---------------------- V6 ----------------------+
7 8
So, below is the minimum spanning tree with no cycles in it.
1 3
+--------------------- V1 -----------------------+
| |
| 5 |
V2 --------------------+ V3
| | |
2 | | | 4
V4 | V5
|
|
V6
+--------------------- V1 -----------------------+
| |
| 5 |
V2 --------------------+ V3
| | |
2 | | | 4
V4 | V5
|
|
V6
The cost of the minimum spanning tree(MST) is the sum of cost of each edge in MST. So, the cost for the above 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
C Program To Implement Minimum Spanning Tree Using Kruskal's Algorithm:
#include <stdlib.h>
struct edge {
int vertex1, vertex2, cost;
struct edge *next;
};
int parentVertices[6], mstCost, count[6];
/* node creation */
struct edge * createNode(int val1, int val2, int cost) {
struct edge *newnode;
newnode = (struct edge *)malloc(sizeof(struct edge));
newnode->vertex1 = val1;
newnode->vertex2 = val2;
newnode->cost = cost;
newnode->next = NULL;
return newnode;
}
/* construct minimum spanning tree */
struct edge * kruskalMST(struct edge *rootNode, int n) {
struct edge *temp = NULL, *x, *y;
int i, parent1, parent2, edgeCount = 0;
for (i = 0; i <= n; i++)
parentVertices[i] = i;
for (i = 0; i <= n; i++)
count[i] = 0;
while((edgeCount < (n - 1)) && rootNode) {
x = rootNode;
rootNode = rootNode->next;
parent1 = parentVertices[x->vertex1];
parent2 = parentVertices[x->vertex2];
/* edge with minimum cost is selected */
if (parent1 != parent2) {
if (parentVertices[x->vertex1] <
parentVertices[x->vertex2]) {
parentVertices[x->vertex2] = x->vertex1;
} else {
parentVertices[x->vertex1] = x->vertex2;
}
edgeCount++;
/* calculating cost of MST */
mstCost = mstCost + x->cost;
if (!temp) {
temp = x;
y = temp;
} else {
y->next = x;
y = y->next;
}
y->next = NULL;
}
}
return temp;
}
void deleteNodes(struct edge *myNode) {
struct edge *temp;
while (myNode != NULL) {
temp = myNode;
myNode = myNode->next;
free(temp);
}
}
int main() {
struct edge *rootNode, *temp;
int i;
/* create adjacency list with edges in sorted order */
rootNode = createNode(2, 1, 1);
rootNode->next = createNode(4, 2, 2);
temp = rootNode->next;
temp->next = createNode(3, 1, 3);
temp = temp->next;
temp->next = createNode(5, 3, 4);
temp = temp->next;
temp->next = createNode(6, 2, 5);
temp = temp->next;
temp->next = createNode(6, 3, 6);
temp = temp->next;
temp->next = createNode(6, 4, 7);
temp = temp->next;
temp->next = createNode(6, 5, 8);
temp->next = NULL;
rootNode = kruskalMST(rootNode, 6);
for (i = 1; i <= 6; i++) {
printf("Parent of %d is %d\n", i, parentVertices[i]);
}
printf("Cost of Minimum Spanning Tree: %d\n", mstCost);
deleteNodes(rootNode);
return 0;
}
Output: (Example Program To Implement MST Using Kruskal's Algorithm)
jp@jp-VirtualBox:~/$ ./a.out
Parent of 1 is 1
Parent of 2 is 1
Parent of 3 is 1
Parent of 4 is 2
Parent of 5 is 3
Parent of 6 is 2
Cost of Minimum Spanning Tree: 15
Parent of 1 is 1
Parent of 2 is 1
Parent of 3 is 1
Parent of 4 is 2
Parent of 5 is 3
Parent of 6 is 2
Cost of Minimum Spanning Tree: 15
No comments:
Post a Comment