Question

Using Kruskal’s Algorithm find the minimum spanning tree of the Graph below.

Requirements…

Show each step but using a priority queue. Where we show each step of the priority queue list. Assume that vertices of an MST are initially viewed as one element sets, and edges are arranged in a priority queue according to their weights. Then, we remove edges from the priority queue in order of increasing weights and check if the vertices incident to that edge is already connected. Show each step as if its Priority queue PLEASE.

W (AB) = 9

W (AC)=7

W (AD)=1

W (AE)=7

W (BD)= 4

W (BF) =8

W (BK)=1

W (BL)=5

W(CF)=7

W(CK)=5

W(DE)=5

W(DF)=1

W(DG)=9

W(DH)=6

W(GJ)=5

W(EF)=7

W(EI)=5

W(FG)=7

W(FH)=4

W(FK)=6

W(GI)=6

W(HK)=1

Answer 1

Kruskal's Algorithm: Sort all the edge weights. As long as the edge is not forming a loop, put it in the spanning tree. Do it till all the sorted edge weights are considered.

Graph: Please ignore the directions

LO LO LO LL LO LO

priority queue = [AD, BK, DF, HK, BD, FH, BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]

Step by Step
[AD, BK, DF, HK, BD, FH, BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> AD in the tree

[BK, DF, HK, BD, FH, BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> BK in the tree

[DF, HK, BD, FH, BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> DF in the tree

[HK, BD, FH, BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> HK in the tree

[BD, FH, BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> BD in the tree

[FH, BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> FH in the tree

[BL, CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> BL in the tree

[CK, DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> CK in the tree

[DE, GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> DE in the tree

[GJ, EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> GJ in the tree

[EI, DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> EI in the tree

[DH, FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> DH forms a loop, ignore

[FK, GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> FK forms a loop, ignore

[GI, AC, AE, CF, EF, FG, BF, AB, DG]
-> GI in the tree

[AC, AE, CF, EF, FG, BF, AB, DG]
-> AC forms a loop, ignore

[AE, CF, EF, FG, BF, AB, DG]
-> AE forms a loop, ignore

[CF, EF, FG, BF, AB, DG]
-> CF forms a loop, ignore

[EF, FG, BF, AB, DG]
-> EF forms a loop, ignore

[FG, BF, AB, DG]
-> FG forms a loop, ignore

[BF, AB, DG]
-> BF forms a loop, ignore

[AB, DG]
-> AB forms a loop, ignore

[DG]
-> DG forms a loop, ignore

[]
-> done

MST after Kruskal's algorith