Survey of Math Chapter 2: Kruskal's Algorithm
Find a minimum-cost spanning tree using Kruskal's algorithm for the following graphs.
Example 1
| Edge | Cost | Included | Reason for Excluding |
|---|---|---|---|
| BC | 4 | YES | |
| AC | 6 | YES | |
| CE | 7 | YES | |
| BD | 8 | YES | |
| BA | 9 | NO | completes a circuit |
| CD | 12 | NO | completes a circuit |
| FE | 12 | YES | DONE |
A minimum-cost spanning tree contains edges BC, AC, CE, BD, and EF and has cost 4+6+7+8+12=37.
Example 2
| Edge | Cost | Included | Reason for Excluding |
|---|---|---|---|
| EF | 4 | YES | |
| EG | 5 | YES | |
| AB | 5 | YES | |
| DE | 5 | YES | |
| FG | 6 | NO | completes a circuit |
| CD | 7 | YES | |
| AC | 7 | YES | |
| BD | 8 | NO | completes a circuit |
| EH | 9 | YES | DONE |
A minimum-cost spanning tree contains edges EF, EG, AB, DE, CD, AC, and EH and has cost 4+5+5+5+7+7+9=42.
