Graphs (Minimum Spanning Trees)

Question 1

What does Prim’s algorithm do?

Answer 1

1. Picks a vertex at random.
2. Finds the minimum edge (seen so far) and adds it.
3. For each vertex in the solution, keep adding by the minimum edge
4. Touches every node with the least amount of weight
   All nodes connectedd to some node once

Question 2

What does Kruskal’s algorithm do?

Answer 2

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.

Question 3

Must all the nodes connect individually?

Answer 3

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.