1
Q
What does Prim’s algorithm do?
A
- Picks a vertex at random.
- Finds the minimum edge (seen so far) and adds it.
- For each vertex in the solution, keep adding by the minimum edge
- Touches every node with the least amount of weight
All nodes connectedd to some node once
2
Q
What does Kruskal’s algorithm do?
A
Sorts the list of edges by increasing weight
Puts each vertex in a disjoint set
Goes through each edge (in sorted order)
If the edge connects to a vertex that is already connected then union it.
Each node gets touched in the system with the least amount of total weights.
3
Q
Must all the nodes connect individually?
A
Each node doesn’t need to be exclusively connected to each node, as long as the nodes are connected in the system. For example, if C is connected to F, and B is connected to C, you don’t have to go out of the way to connect B to F because they are already connected in the system.
