Graph traversal forms the basis of countless algorithms. Breadth-First Search (BFS) explores level by level using a queue, making it ideal for shortest path in unweighted graphs, level-order traversals, and bipartite checks. Depth-First Search (DFS) goes as deep as possible before backtracking, expressed elegantly either recursively or iteratively with a stack. DFS underlies cycle detection, topological sorting, strongly connected components, and solving maze problems. Both traversals run in O(V + E) time.
Shortest path algorithms address weighted graphs. Dijkstra's algorithm with a min-heap finds shortest paths from a source in O((V + E) log V) for graphs with non-negative weights. Bellman-Ford handles negative weights in O(V × E) and detects negative cycles. Floyd-Warshall computes all-pairs shortest paths in O(V³). A* search extends Dijkstra with a heuristic for faster goal-directed search, optimal when the heuristic is admissible. SPFA offers practical speedups over Bellman-Ford by only relaxing edges from recently updated nodes.
Minimum Spanning Trees (MST) connect all vertices with minimum total weight. Kruskal's algorithm sorts edges and greedily adds them if they don't form a cycle, using Union-Find for cycle detection. Prim's algorithm grows the MST from a starting vertex, adding the cheapest edge to an unvisited vertex via a min-heap. Advanced graph topics include finding articulation points and bridges (critical nodes/edges whose removal disconnects the graph) using DFS with discovery times and low-link values. Tarjan's and Kosaraju's algorithms find strongly connected components in O(V + E), while topological sort using Kahn's algorithm processes nodes with in-degree zero to detect cycles. Maximum flow algorithms like Edmonds-Karp and Dinic's solve network flow problems with applications in bipartite matching and scheduling.