Graphs Beyond Traversal Checkpoint

1. Kruskal's algorithm builds an MST by:

Sorting edges and adding if they do not form a cycle Running BFS from every node Relaxing edges repeatedly Only choosing smallest degree nodes

2. An MST of a connected graph with n nodes has exactly ____ edges.

3. Kosaraju's algorithm requires DFS on the:

Reversed graph in decreasing finish order Undirected version of the graph Graph after removing back edges Graph sorted by degree

4. Hopcroft-Karp runs in:

O(E sqrt V) O(EV) O(V^3) O(E log V)