Kruskal's algorithm is an algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a safe edge to add to the growing forest by finding, of all the edges that connects any two trees in the forest, an edge $(u,v)$ of least weight. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
The given graph is
![](https://gateoverflow.in/?qa=blob&qa_blobid=12919328135548667607)
We can see that $DB's$ weight is not given.
We know that, for any weighted graph, if the weight of an certain edge isn't given, then the weight'll be $1$(default)
Edge No. |
Vertex Pair |
Edge Weight |
E1 |
(B,D) |
1 |
E2 |
(G,C) |
2 |
E3 |
(A,D) |
2 |
E4 |
(B,G) |
3 |
E5 |
(A,G) |
3 |
E6 |
(A,E) |
4 |
E7 |
(D,G) |
4 |
E8 |
(B,C) |
4 |
E9 |
(B,F) |
4 |
E10 |
(D,E) |
5 |
E11 |
(C,F) |
5 |
E12 |
(A,C) |
6 |
Graph
![](https://gateoverflow.in/?qa=blob&qa_blobid=15070132264584151939)
Add edge E1
![](https://gateoverflow.in/?qa=blob&qa_blobid=14175470042053729791)
Add edge E2
![](https://gateoverflow.in/?qa=blob&qa_blobid=13346080850538613401)
Add edge E3
![](https://gateoverflow.in/?qa=blob&qa_blobid=7447646606215530586)
Add edge E4
![](https://gateoverflow.in/?qa=blob&qa_blobid=12652879061894244738)
Edge E5 will not counted, as it'll create cycle.
Add edge E6
![](https://gateoverflow.in/?qa=blob&qa_blobid=13966471820411087141)
Edge E7,E8 will not counted, as it'll create a cycle.
Add edge E9
![](https://gateoverflow.in/?qa=blob&qa_blobid=4157421304135738114)
Edge E10, E11, E12 will not connected, they'll make a cycle.
∴ $\color{green}{\text{Total Cost}}= 1+2+2+3+4+4$
$\qquad\qquad = \color{gold}{16}$
$\color{violet}{\text{The List of the edges of the tree in the order in which they are choosen is}}$ $\color{maroon}{\text{BD, GC, AD, BG, AE, BF}}$