Minimum Spanning Tree

Question 1

What DS does Prim’s algorithm work?

Answer 1

Priority Queue to store the edges and Array to track if a vertex has been visited.

Question 2

How does Prim’s algorithm work?

Answer 2

1. Start from a vertex and mark it as visited
2. Queue all of its edges into PQ that’s sorted by edge weight
3. Dequeue the edge that has the minimum weight
4. If the vertex has already been visited, skip and poll the next edge
5. Else, add that vertex to the tree
6. Queue all of that vertex’s edges into PQ
7. Repeat until all vertices have been added

Question 3

Time Complexity of Prim’s

Answer 3

O(ElogV)

Question 4

What DS does Kruskal’s algorithm use?

Answer 4

UFDS and Edge List

Question 5

How does Kruskal’s algorithm work?

Answer 5

Keep picking the edge of lowest weight to be part of the MST, with the condition that the edge must be connecting our current tree to a previously connected vertex, until all vertices are connected to the tree.

1. Sort the set of edges by increasing weight
2. While there are unprocessed edges left, pick an unprocessed edge e with min cost
3. If adding e to T does not form a cycle, add e to T

Question 6

Time Complexity of Kruskal’s

Answer 6

O(ElogV)

Question 7

How to find the minimax path from a to b?

Answer 7

Find the MST and find the path between a and b. This is the minimax path between a and b.

Question 8

Properties of a graph where you’d find MST

Answer 8

Connected, undirected, weighted