3.2 Adjacency lists and edge lists

Graph representation techniques are crucial for efficiently storing and manipulating graph structures in computer memory. Adjacency lists, a popular method, offer a space-efficient solution for sparse graphs by storing only connected vertices for each node.

This approach allows for quick access to a vertex's neighbors, making it ideal for many graph algorithms. We'll explore the construction, space complexity, and implementation of adjacency lists, comparing them to other representations like edge lists and matrices.

Graph Representation Techniques

Adjacency lists for graph representation

• Adjacency lists efficiently store graph structure using lists of adjacent vertices for each vertex
• Implemented as array or hash table of linked lists enhances flexibility and performance
• Lists contain only directly connected vertices reducing memory usage for sparse graphs
• Efficient for sparse graphs with few edges compared to total possible connections
• Space-efficient representation especially beneficial for large, sparse networks (social networks)
• Less efficient for dense graphs where most vertices are connected to each other
• Checking edge existence takes $O(d)$ time where $d$ is vertex degree potentially slower for high-degree vertices

Construction of adjacency lists

• Undirected graphs require each edge to appear in two lists maintaining symmetry
• Directed graphs list edges in only one direction following edge orientation
• Weighted graphs store weight with adjacent vertex using pairs or custom objects (vertex, weight)
• Construction process:
  1. Initialize empty lists for each vertex
  2. Iterate through edges, adding vertices to appropriate lists
  3. For undirected graphs, add both vertices for each edge ensuring bidirectional representation

Space complexity: Lists vs matrices

• Adjacency list space complexity $O(V + E)$ scales with actual graph structure
• Adjacency matrix space complexity $O(V^2)$ regardless of edge count
• Lists more efficient for sparse graphs common in real-world applications (road networks)
• Matrices potentially more efficient for very dense graphs rare in practice
• Lists scale better with increasing graph size for most applications (social networks, web graphs)

Edge lists and adjacency lists

• Edge lists store all edges in single list or array simple and straightforward
• Each element contains source vertex, destination vertex, and weight if applicable
• Can be used to construct adjacency lists by grouping edges by source vertex
• Adjacency lists provide faster access to vertex neighbors beneficial for many algorithms
• Edge lists suitable for algorithms processing all edges sequentially (Kruskal's algorithm)
• Efficient for adding or removing edges without restructuring entire representation

Implementation with graph data structures

• Depth-First Search (DFS) with adjacency lists iterates through neighbor lists recursively or using stack
• Breadth-First Search (BFS) uses queue to explore all neighbors before moving to next level
• Dijkstra's algorithm with adjacency lists uses priority queue to select next vertex, updates distances by iterating neighbor lists
• Kruskal's algorithm with edge lists sorts edges by weight, uses disjoint-set data structure for cycle detection
• Prim's algorithm with adjacency lists uses priority queue for edge selection, updates key values through neighbor iteration