Graph Algorithms

Introduction

Graph algorithms: core tools to analyze discrete structures modeled as graphs. Used in computer networks, scheduling, optimization, and more. Problems: pathfinding, connectivity, flow, cycles. Methods: combinatorial, greedy, dynamic programming.

"Graphs are the language of networks and relationships. Their algorithms unlock insights into complex systems." -- Reinhard Diestel

Graph Representations

Adjacency Matrix

Definition: n×n matrix A with A[i][j] = 1 if edge (i, j) exists, else 0. Space: O(n²). Access: O(1). Best for dense graphs.

Adjacency List

Definition: array of lists, each list contains neighbors of vertex. Space: O(n + m) where m = edges. Access: O(degree). Best for sparse graphs.

Edge List

Definition: list of all edges (u, v). Space: O(m). Useful for algorithms needing edge manipulation.

Comparison Table

Traversal Algorithms

Breadth-First Search (BFS)

Explores vertices level by level. Uses queue. Time: O(n + m). Applications: shortest path in unweighted graphs, connectivity.

Depth-First Search (DFS)

Explores as deep as possible before backtracking. Uses stack or recursion. Time: O(n + m). Applications: cycle detection, topological sorting.

Iterative vs Recursive DFS

Recursive: simple, risk stack overflow. Iterative: uses explicit stack, safer for deep graphs. Both have same complexity.

BFS Algorithm

function BFS(graph, start): queue ← empty queue enqueue start into queue mark start as visited while queue not empty: vertex ← dequeue queue for each neighbor of vertex: if neighbor not visited: mark neighbor visited enqueue neighbor

Shortest Path Algorithms

Dijkstra's Algorithm

Finds shortest paths from source to all vertices in weighted graphs with non-negative edges. Uses priority queue. Time: O(m + n log n).

Bellman-Ford Algorithm

Handles graphs with negative weights, detects negative cycles. Time: O(nm). Iterative relaxation of edges.

Floyd-Warshall Algorithm

All-pairs shortest paths. Uses dynamic programming. Time: O(n³). Handles negative weights without negative cycles.

Dijkstra's Algorithm Pseudocode

function Dijkstra(graph, source): dist[] ← ∞ for all vertices dist[source] ← 0 priorityQueue ← all vertices with dist values while priorityQueue not empty: u ← vertex with smallest dist in priorityQueue remove u from priorityQueue for each neighbor v of u: alt ← dist[u] + weight(u,v) if alt < dist[v]: dist[v] ← alt update priorityQueue with dist[v]

Minimum Spanning Trees

Definition

MST: subset of edges connecting all vertices with minimum total weight, no cycles.

Kruskal's Algorithm

Greedy: sorts edges by weight, adds if no cycle. Uses union-find. Time: O(m log m).

Prim's Algorithm

Starts from a vertex, grows MST by adding minimum weight edge connecting new vertex. Uses priority queue. Time: O(m + n log n).

MST Algorithm Comparison Table

Network Flow

Maximum Flow Problem

Find maximum feasible flow from source to sink in a flow network with capacity constraints.

Ford-Fulkerson Method

Augments flows along paths in residual graph. Time: O(max_flow × m). Non-polynomial in worst case.

Edmonds-Karp Algorithm

Ford-Fulkerson variant using BFS for shortest augmenting paths. Time: O(n m²).

Dinic's Algorithm

Uses layered network and blocking flows. Time: O(min(n^(2/3), m^(1/2)) m) for unit capacities.

Ford-Fulkerson Pseudocode

function FordFulkerson(graph, source, sink): flow ← 0 while path from source to sink exists in residual graph: find path p using DFS or BFS residual_capacity ← min capacity along p augment flow along p by residual_capacity update residual graph flow ← flow + residual_capacity return flow

Cycle Detection

In Undirected Graphs

Use DFS with parent tracking. Cycle if back edge detected.

In Directed Graphs

Use DFS with recursion stack tracking. Cycle if vertex revisited in recursion stack.

Union-Find Approach

For undirected graphs. Union sets of connected vertices. Cycle if union on same set.

Topological Sorting

Definition

Linear ordering of vertices in Directed Acyclic Graph (DAG) where edges go from earlier to later vertices.

Kahn's Algorithm

Iteratively removes vertices with zero in-degree. Uses queue. Time: O(n + m).

DFS Based Algorithm

Performs DFS, pushes vertices post-recursion. Reverse order is topological sort. Time: O(n + m).

Kahn's Algorithm Pseudocode

function KahnTopologicalSort(graph): inDegree[] ← count of incoming edges per vertex queue ← vertices with inDegree 0 list ← empty while queue not empty: u ← dequeue queue append u to list for each neighbor v of u: inDegree[v] ← inDegree[v] - 1 if inDegree[v] == 0: enqueue v if list size < number of vertices: return "Cycle detected" else: return list

Connectivity

Connected Components

Subgraphs where any two vertices are connected by paths. Found using DFS or BFS.

Strongly Connected Components (SCC)

In directed graphs, maximal subgraphs where each vertex reachable from any other. Algorithms: Kosaraju, Tarjan.

Tarjan's Algorithm

DFS-based, uses low-link values to identify SCCs in O(n + m) time.

Planar Graph Algorithms

Planarity Testing

Checks if graph can be drawn without edge crossings. Algorithms: Hopcroft-Tarjan, Boyer-Myrvold.

Graph Coloring

Assign colors to vertices so adjacent vertices differ. Four color theorem applies to planar graphs.

Planar Separator Theorem

Planar graphs can be split into roughly equal parts by removing O(√n) vertices. Used in divide and conquer.

Algorithm Complexity

Time Complexity

Depends on graph size parameters: n = vertices, m = edges. Linear: O(n + m), polynomial, exponential.

Space Complexity

Storage for graph representation, auxiliary data structures like queues, stacks, heaps.

NP-Completeness in Graph Problems

Many graph problems are NP-complete: Hamiltonian path, graph coloring, clique detection. Approximation or heuristics used.

Complexity Classes Table

Applications

Computer Networks

Routing protocols use shortest path algorithms. Network reliability analyzed via connectivity.

Scheduling and Dependency Resolution

Topological sorting orders tasks with dependencies. Cycle detection prevents deadlocks.

Operations Research

Network flow models supply chains and traffic, solved by max-flow algorithms.

Social Network Analysis

Connectivity, centrality, and community detection use graph algorithms extensively.

Computational Biology

Graph alignment, phylogenetic trees, and interaction networks modeled using graph theory.

References

• Diestel, Reinhard. Graph Theory. Springer, 5th Edition, 2017, pp. 1-400.
• Cormen, Thomas H., et al. Introduction to Algorithms. MIT Press, 3rd Edition, 2009, pp. 595-650.
• Tarjan, Robert E. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, vol. 1, no. 2, 1972, pp. 146-160.
• Ford, L. R., and D. R. Fulkerson. Maximal Flow Through a Network. Canadian Journal of Mathematics, vol. 8, 1956, pp. 399-404.
• Hopcroft, John E., and Robert E. Tarjan. Efficient Planarity Testing. Journal of the ACM, vol. 21, no. 4, 1974, pp. 549-568.