Introduction
Graph representation: core technique in data structures. Purpose: model relationships, dependencies, and networks. Selection criteria: graph size, edge density, operation types. Trade-offs: memory usage, access speed, update efficiency. Common forms: adjacency matrix, adjacency list, incidence matrix.
"Choosing the right graph representation is critical for algorithm efficiency and memory optimization." -- Robert Sedgewick
Graph Fundamentals
Definition
Graph G = (V, E): set of vertices V and edges E. Vertex: node or point. Edge: connection between vertex pairs. Types: directed (arcs), undirected (edges).
Terminology
Degree: number of edges incident on vertex. In-degree/out-degree: for directed graphs. Path: sequence of edges connecting vertices. Cycle: path starting and ending at same vertex.
Applications
Networks: social, communication, transportation. Dependency graphs: compilers, tasks. Modeling: biological, chemical interactions.
Adjacency Matrix
Structure
2D array of size |V| x |V|. Entry at (i, j): 1 if edge from vertex i to j exists, else 0 (unweighted). For weighted graphs: store edge weights.
Properties
Space complexity: O(V²). Fast edge lookup: O(1). Inefficient for sparse graphs. Symmetric matrix for undirected graphs.
Example
| Vertex | A | B | C |
|---|---|---|---|
| A | 0 | 1 | 0 |
| B | 1 | 0 | 1 |
| C | 0 | 1 | 0 |
Adjacency List
Structure
Array or list of vertices with linked lists or arrays of adjacent vertices. Each vertex stores a list of neighbors.
Properties
Space complexity: O(V + E). Efficient for sparse graphs. Edge lookup: O(degree of vertex). Easier to iterate over neighbors.
Example
Vertex: Adjacent verticesA: BB: A, CC: BIncidence Matrix
Structure
2D array of size |V| x |E|. Rows represent vertices, columns represent edges. Entries: 1 if vertex incident on edge, 0 otherwise. For directed graphs: 1 for edge leaving vertex, -1 for edge entering vertex.
Properties
Space complexity: O(V x E). Less common than adjacency structures. Useful for certain algebraic graph algorithms.
Example
| Vertex/Edge | e1 | e2 | e3 |
|---|---|---|---|
| A | 1 | 0 | 0 |
| B | 1 | 1 | 0 |
| C | 0 | 1 | 1 |
Edge List
Structure
List or array storing all edges explicitly as pairs or tuples (u, v). May include weights.
Properties
Simple to implement. Space complexity: O(E). Inefficient for adjacency queries. Useful for algorithms needing edge iteration.
Example
Edges:(A, B)(B, C)(C, A)Directed vs Undirected Graphs
Directed Graphs
Edges have direction: (u, v) ≠ (v, u). Represent relationships with orientation. Adjacency matrix asymmetric.
Undirected Graphs
Edges bidirectional: (u, v) = (v, u). Symmetric adjacency matrix. Common in social, communication networks.
Representation Differences
Adjacency list for directed graphs: store outgoing edges. For undirected: store neighbors symmetrically.
Weighted Graphs
Definition
Edges assigned numeric weights: costs, distances, capacities. Used in shortest path, flow algorithms.
Representation
Adjacency matrix stores weights or ∞ for no edge. Adjacency list stores (vertex, weight) pairs.
Example
Adjacency List with weights:A: (B, 5)B: (C, 3)C: (A, 8)Sparse vs Dense Graphs
Sparse Graphs
Few edges relative to vertices: E ≈ O(V). Efficiently stored with adjacency lists.
Dense Graphs
Many edges: E ≈ O(V²). Adjacency matrix preferred for constant time edge queries.
Selection Criteria
Memory constraints: sparse → adjacency list. Access patterns: dense → adjacency matrix.
Graph Traversal Implications
Traversal Algorithms
BFS and DFS require quick access to neighbors. Adjacency list suits neighbor iteration. Adjacency matrix provides rapid presence checks.
Performance Impact
Adjacency list traversal: O(V + E). Adjacency matrix traversal: O(V²). Sparse graphs benefit from adjacency lists.
Algorithm Suitability
Pathfinding, connectivity checks prefer adjacency list for large sparse graphs. Dense graphs tolerate matrix overhead.
Complexity Comparisons
Memory Complexity
Adjacency matrix: O(V²). Adjacency list: O(V + E). Incidence matrix: O(V x E). Edge list: O(E).
Edge Lookup Time
Matrix: O(1). List: O(degree of vertex). Edge list: O(E).
Iteration Over Neighbors
List: O(degree). Matrix: O(V). Incidence: O(E).
Summary Table:| Representation | Memory | Edge Lookup | Neighbor Iteration ||------------------|---------------|-------------|--------------------|| Adjacency Matrix | O(V²) | O(1) | O(V) || Adjacency List | O(V+E) | O(d) | O(d) || Incidence Matrix | O(V x E) | O(V) | O(E) || Edge List | O(E) | O(E) | O(E) |Practical Applications
Network Routing
Weighted graphs used in shortest path algorithms (Dijkstra, Bellman-Ford). Representation impacts speed.
Social Networks
Sparse, large graphs. Adjacency lists preferred for memory efficiency and neighbor queries.
Compiler Design
Dependency graphs: directed acyclic graphs (DAGs). Edge lists or adjacency lists common for task scheduling.
References
- R. Sedgewick, K. Wayne, "Algorithms," Addison-Wesley, 4th Ed., 2011, pp. 657-720.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to Algorithms," MIT Press, 3rd Ed., 2009, pp. 596-645.
- C. A. R. Hoare, "Efficient Graph Representations," Communications of the ACM, vol. 17, no. 6, 1974, pp. 330-336.
- J. Gross, J. Yellen, "Graph Theory and Its Applications," CRC Press, 2nd Ed., 2005, pp. 23-57.
- U. Brandes, T. Erlebach (Eds.), "Network Analysis: Methodological Foundations," Springer, 2005, pp. 3-29.