YUNOVA · Data Structures & Algorithms
Module 12: Advanced graphs
Minimum spanning tree: Prim and Kruskal
Key points
- A minimum spanning tree connects all vertices with least total edge weight.
- Kruskal sorts edges and adds each one that does not form a cycle, using DSU.
- Prim grows the tree from one vertex using a priority queue.
Disjoint set union (Union-Find)
Key points
- DSU keeps elements in disjoint sets with find and union operations.
- Path compression and union by rank make operations nearly constant time.
- It is used for cycle detection and Kruskal's algorithm.
Bellman-Ford and Floyd-Warshall
Key points
- Bellman-Ford finds single-source shortest paths and works with negative edges.
- Relaxing all edges V-1 times is enough; any further improvement means a negative cycle.
- Floyd-Warshall finds all-pairs shortest paths in O(V³).
Strongly connected components: Kosaraju
Key points
- In a strongly connected component every vertex can reach every other vertex.
- Kosaraju runs DFS to get finish order, then DFS on the reversed graph in that order.
- It runs in O(V + E).