Kruskal's and Prim's algorithms
The minimum spanning tree of a weighted graph: Kruskal's algorithm (edges by increasing weight, refusing those that close a cycle), Prim's (growth from one vertex), the greedy justification and uniqueness.
- 29 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Understand
A few cards from the deck
Minimum spanning tree: what is it?
Show the answer
A spanning tree of a connected weighted graph whose edges have the smallest possible total weight.
It is the answer to the cheapest wiring that links all the points. There are sometimes several, all with the same weight.
Six buildings A to F, possible links and cost: A-B 7, A-C 3, B-C 5, B-D 4, C-D 8, C-E 6, D-E 2, D-F 9, E-F 1. Which is the first edge Kruskal refuses?
- C-E (6)
- A-B (7)
- C-D (8)
- D-F (9)
Show the answer
C-E (6)
In order: E-F 1, D-E 2, A-C 3, B-D 4 and B-C 5 are kept. At C-E (6), C is already linked to E through B, D: refused. A-B, C-D and D-F will be refused too, but later.
Kruskal sorts the edges by … weight and refuses any edge whose two ends are already in the ….
Show the answer
Kruskal sorts the edges by increasing weight and refuses any edge whose two ends are already in the same class.
Two ends in the same class are already linked by kept edges: adding the edge would close a cycle.
Greedy algorithm: what is it?
Show the answer
A strategy that builds a solution by making, at each step, the choice that looks best at the time, and never revisiting it.
For the minimum spanning tree this local choice is proven optimal. For other problems, it can give a valid solution that is not the best.