1. Graph Algorithms
Graph algorithms operate on \(G = (V, E)\) where \(V\) is a finite set of vertices and \(E \subseteq V \times V\) is a set of edges. They model an enormous range of real-world structures: road networks, circuit boards, dependency trees, social networks, and compiler flow graphs.
1.1 Algorithms
| Algorithm | Problem | Paradigm | Complexity |
|---|---|---|---|
| Breadth-First Search | Reachability, unweighted shortest paths | Uninformed traversal | \(O(V + E)\) |
| Depth-First Search | Connectivity, topological sort, SCC | Uninformed traversal | \(O(V + E)\) |
| Dijkstra's Algorithm | Weighted shortest paths (non-negative) | Greedy | \(O((V + E) \log V)\) |
| Kruskal's Algorithm | Minimum spanning tree | Greedy (Union-Find) | \(O(E \log E)\) |
| Prim's Algorithm | Minimum spanning tree | Greedy (priority queue) | \(O((V + E) \log V)\) |
1.2 Key Data Representations
- Adjacency list: \(O(V + E)\) space; preferred for sparse graphs. Edge traversal costs \(O(\deg(v))\) per vertex.
- Adjacency matrix: \(O(V^2)\) space; preferred for dense graphs and algorithms that test edge existence in \(O(1)\) (e.g. Floyd–Warshall).
- Edge list: \(O(E)\) space; natural for Kruskal's algorithm, which sorts edges.