Graph Algorithms

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure (often implemented using recursion) to keep track of vertices to visit next. DFS has applications in topological sorting, finding connected components, solving mazes, and detecting cycles in graphs.

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the present depth level before moving on to vertices at the next depth level. It uses a queue to keep track of the next vertices to visit, ensuring that vertices are visited in order of their distance from the source vertex. BFS is commonly used for finding the shortest path in unweighted graphs, connected components, and solving puzzles with the fewest possible moves.

Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It works by maintaining a set of vertices whose shortest distance from the source is already known and repeatedly selecting the vertex with the minimum distance value, updating the distance values of its adjacent vertices. Dijkstra's algorithm is widely used in network routing protocols and as a subroutine in other graph algorithms.

Topological Sort is an algorithm for ordering the vertices of a directed acyclic graph (DAG) such that for every directed edge (u,v), vertex u comes before vertex v in the ordering. This algorithm is essential for scheduling tasks with dependencies, course prerequisites planning, and compilation sequence determination. A graph must have no directed cycles to have a valid topological ordering, making this algorithm a useful tool for cycle detection as well.

Bellman-Ford computes shortest paths from a single source to every other vertex in a weighted graph, even when some edge weights are negative. It works by relaxing all edges repeatedly: after V-1 passes the distances are guaranteed correct if no negative cycle is reachable from the source. Slower than Dijkstra at O(V·E) but more general — and a single extra pass detects negative cycles. Used in distance-vector routing protocols and as the inner loop of Johnson's algorithm.

Prim's algorithm builds a minimum spanning tree (MST) by starting at an arbitrary vertex and repeatedly adding the cheapest edge that connects the existing tree to a vertex outside it. Each step strictly grows the tree by one vertex until every vertex is included. The greedy choice is provably optimal because of the cut property of MSTs. Common applications include network design, clustering, and approximation algorithms for the traveling salesman problem.

Kruskal's algorithm builds a minimum spanning tree (MST) by sorting all edges by weight and adding them one at a time, skipping any edge that would form a cycle. A disjoint-set (union-find) data structure makes the cycle check efficient. Unlike Prim's, Kruskal's grows the tree as a forest of components that gradually merge, making it well-suited to sparse graphs. It's used in network design, image segmentation, and as a building block for clustering algorithms.