- Spanning tree is a subgraph ,which is also a tree,that has all the vertices that is included in the original graph and they vertices are all connected.
- If the Original graph has n vertices subgraph has,
n vertices
n-1 edges
- And minimum spanning tree is a subgraph such that,
Single paths exist.
out of all the available paths between two given points ,the path that cost the minimum.
- Kruskal is a minimum spanning tree algorithm.Basically what Kruskal does is scan all the edges and arrange them in ascending order considering the weight values.Select the edges one by one from the lowest weight and if it does not create a cycle in the subgraph add it.The algorithm continues till the no,of edges of the subgraph is equal to n-1(n=vertices).
- After sorting out the edges in ascending order.
- The original graph contains 9 vertices so the minimum spanning tree should have 9 vertices and 8 edges.
- Now we have to pick all the edges in the sorted list and add them to the graph
2.
3.
4.
6.
7.
8.
9.
10.
11.
12.
- Since the no.of edges is equal to 8 the algorithm stops here.
