Spanning tree
Aspanning tree isasub-graph of an undirected connected graph, which includes
all the vertices of the graph with a minimum possible number of edges. If a vertex
is missed, then it is not a spanning tree.
The edges may or may not have weights assigned to them.
The total number of spanning trees with n Vertices that can be created from a
complete graph is equal to n),
If we have n = 4, the maximum number of possible spanning trees is equal to 4: =
16. Thus, 16 spanning trees can be formed from a complete graph with 4 vertices.
Minimum Spanning Tree
A mininmum spanning tree is a spanning tree in which the sum of the weight of the
edges is as minimum as possible.
9
15
11 10
7
Kruskal's Minimum Spanning Tree (MST) Algorithm
A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected,
undirected graph is a spanning tree with a weight less than or equal to the weight of every other
spanning tree.
Introduction to Kruskal's Algorithm:
Here we willdiscuss Kruskal's algorithm to find the MST of a given weighted graph.
, In Kruskal's algorithm, sort all edges of the given graph in increasing order. Then it keeps on adding
new edges and nodes in the MST if the newly added edge does not form a cycle. It picks the minimum
weighted edge at first and the maximum weighted edge at last. Thus we can say that it makes a locally
optimal choice in cach step in order to find the optimal solution.
How to find MST using Kruskal's algorithm?
Below are the steps for finding MST using Kruskal's algorithm:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallost odgo. Chock if it forms a cyelo with the spanning troo formod so far. If
the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
Illustration:
Below is the illustration of the above approach:
Input Graph:
7
4 9
2
4
11 8 14
6
10
6
1 2
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having
(9- 1) = 8 edges.
After sorting:
Weight Source Destination
7 6
2 8 2
2 6 5
4 1
4 2 5
6 8 6
7 2 3
Aspanning tree isasub-graph of an undirected connected graph, which includes
all the vertices of the graph with a minimum possible number of edges. If a vertex
is missed, then it is not a spanning tree.
The edges may or may not have weights assigned to them.
The total number of spanning trees with n Vertices that can be created from a
complete graph is equal to n),
If we have n = 4, the maximum number of possible spanning trees is equal to 4: =
16. Thus, 16 spanning trees can be formed from a complete graph with 4 vertices.
Minimum Spanning Tree
A mininmum spanning tree is a spanning tree in which the sum of the weight of the
edges is as minimum as possible.
9
15
11 10
7
Kruskal's Minimum Spanning Tree (MST) Algorithm
A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected,
undirected graph is a spanning tree with a weight less than or equal to the weight of every other
spanning tree.
Introduction to Kruskal's Algorithm:
Here we willdiscuss Kruskal's algorithm to find the MST of a given weighted graph.
, In Kruskal's algorithm, sort all edges of the given graph in increasing order. Then it keeps on adding
new edges and nodes in the MST if the newly added edge does not form a cycle. It picks the minimum
weighted edge at first and the maximum weighted edge at last. Thus we can say that it makes a locally
optimal choice in cach step in order to find the optimal solution.
How to find MST using Kruskal's algorithm?
Below are the steps for finding MST using Kruskal's algorithm:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallost odgo. Chock if it forms a cyelo with the spanning troo formod so far. If
the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
Illustration:
Below is the illustration of the above approach:
Input Graph:
7
4 9
2
4
11 8 14
6
10
6
1 2
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having
(9- 1) = 8 edges.
After sorting:
Weight Source Destination
7 6
2 8 2
2 6 5
4 1
4 2 5
6 8 6
7 2 3
