Graph Data Structures: Representations, Storage, and Traversals

A Graph is a non-linear data structure consisting of a finite set of vertices (or nodes) $V$ and a set of edges $E$ that connect pairs of vertices: $G = (V, E)$. Unlike trees, graphs do not have a root node, can contain cycles, and allow multiple arbitrary paths between nodes.

Graphs are the foundational structure for modeling networked relationships, including social networks, transportation and road networks, recommendation engines, dependency resolution systems, and internet routing protocols.

Classifications and Terminology

• Directed vs. Undirected: In an undirected graph, edges are bidirectional (u - v is symmetric). In a directed graph (Digraph), edges have explicit directional flow (u -> v does not imply v -> u).
• Weighted vs. Unweighted: Weighted graphs assign numerical costs or distances to edges; unweighted graphs treat all connections uniformly.
• Cyclic vs. Acyclic: A cyclic graph contains at least one path where a node can reach itself. A Directed Acyclic Graph (DAG) contains no closed loops and serves as the model for task scheduling and version control graphs (e.g., Git).
• Degree: In undirected graphs, the degree is the number of incident edges. In directed graphs, this splits into In-Degree (incoming edges) and Out-Degree (outgoing edges).

Graph Storage Representations: Matrix vs. List

1. Adjacency Matrix

A 2D array of dimensions V x V where matrix[i][j] is 1 (or the edge weight) if an edge exists from vertex i to vertex j, and 0 otherwise.

• Space Complexity: O(V^2), independent of the number of edges.
• Edge Lookup: O(1) instantaneous check for edge existence.
• Finding Neighbors: O(V) scan across a full row.
• Best For: Dense graphs where E is close to V^2.

2. Adjacency List

An array or hash map of size V, where each element points to a dynamic list (vector or linked list) containing only the vertices adjacent to that node.

• Space Complexity: O(V + E) for directed graphs, O(V + 2E) for undirected graphs.
• Edge Lookup: O(degree(u)) to find if edge (u, v) exists.
• Finding Neighbors: O(degree(u)) by iterating directly over the node's list.
• Best For: Sparse graphs where E is much smaller than V^2 (standard in real-world networks).

Core Graph Traversal Algorithms

1. Breadth-First Search (BFS)

BFS traverses the graph layer-by-layer, exploring all immediate neighbors of the current vertex before moving deeper. It utilizes a Queue (FIFO) and a boolean visited array to avoid revisiting nodes and infinite loops in cyclic graphs.

• Time Complexity: O(V + E) with Adjacency List; O(V^2) with Adjacency Matrix.
• Space Complexity: O(V) for the queue and visited state.
• Key Property: Finds the shortest path in unweighted graphs.

2. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It can be implemented recursively using the system call stack or iteratively using an explicit Stack (LIFO) alongside a visited tracker.

• Time Complexity: O(V + E) with Adjacency List; O(V^2) with Adjacency Matrix.
• Space Complexity: O(V) in the worst case (e.g., skewed linear chain graph).
• Key Property: Ideal for cycle detection, topological sorting, connected components, and maze/puzzle exploration.

Real-World Applications & Advanced Algorithms

1. Topological Sorting (Kahn's Algorithm / DFS): Scheduling build systems (e.g., Make, Webpack) and prerequisite course pipelines.
2. Shortest Path Finding: Dijkstra's algorithm for weighted non-negative edges; Bellman-Ford for negative weight cycles.
3. Minimum Spanning Trees (MST): Kruskal's and Prim's algorithms for designing low-cost physical cable and pipe layouts.
4. Connected Components & Cycle Detection: Disjoint Set Union (DSU) and Kosaraju's/Tarjan's strongly connected components (SCC) algorithms.