DS: Graph Representation with Adjacency Multilist

The adjacency list is a classic, versatile representation for graphs, but for certain algorithms, its duplication of edge data can be inefficient. The adjacency multilist is a specialized structure designed to eliminate this redundancy by storing each edge exactly once, making it exceptionally efficient for algorithms that need to traverse or mark edges directly. Understanding this representation sharpens your data structure design skills, demonstrating how the choice of underlying model can dramatically optimize memory usage and simplify complex graph operations like edge deletion and cycle detection.

From Adjacency List to Adjacency Multilist

To appreciate the multilist, you must first recall the standard adjacency list. In this representation, each vertex in the graph maintains a linked list of its neighboring vertices. For an undirected graph with $E$ edges, this results in $2E$ node entries across all lists because the edge $(u,v)$ appears in both the list for vertex $u$ and the list for vertex $v$. This duplication is simple but wasteful for memory and complicates operations on the edge itself, as you would need to locate and update two separate nodes.

The adjacency multilist solves this by storing each edge in a single, shared node. This node resides in multiple lists—specifically, in the adjacency lists of the two vertices it connects. The core idea is that an edge is a first-class object, not just a mention in a vertex's neighbor roster. This single representation allows you to mark an edge as visited or delete it by modifying a single node, a significant advantage for algorithms like depth-first search or finding minimum spanning trees where edge states are critical.

Structure of a Multilist Node

In an adjacency multilist for an undirected graph, a single node structure represents one edge. This node typically contains four essential fields (for a vertex-indexed implementation):

• vertex_i: One endpoint of the edge.
• vertex_j: The other endpoint of the edge.
• next_i: A pointer/reference to the next node in the adjacency list of vertex_i.
• next_j: A pointer/reference to the next node in the adjacency list of vertex_j.

Conceptually, this single node is threaded into two different linked lists. The next_i pointer chains it with other edges incident to vertex_i, while the next_j pointer chains it with other edges incident to vertex_j. This is the "multi" in multilist. For implementation, you typically maintain an array of vertices, where each vertex points to the head of a linked list of edge nodes where that vertex is an endpoint. The node itself tells you which pointer (next_i or next_j) to follow to continue traversing a specific vertex's list.

Building and Traversing a Multilist

Let's construct a multilist for a small graph. Consider an undirected graph with vertices {0, 1, 2, 3} and edges: (0,1), (0,2), (1,2), (2,3).

1. Create Edge Nodes: For edge (0,1), create node A: vertex_i=0, vertex_j=1. For edge (0,2), create node B: vertex_i=0, vertex_j=2. For edge (1,2), create node C: vertex_i=1, vertex_j=2. For edge (2,3), create node D: vertex_i=2, vertex_j=3.
2. Link into Vertex Lists:

• Vertex 0's List: It is involved in edges A (as i) and B (as i). We link them: Vertex[0] -> A. In node A, since vertex_i=0, we use next_i to point to node B. In node B, vertex_i=0, so its next_i is set to NULL.
• Vertex 1's List: Involved in edges A (as j) and C (as i). Vertex[1] -> A. In node A, vertex_j=1, so next_j points to node C. In node C, vertex_i=1, so its next_i is set to NULL.
• Vertex 2's List: Involved in edges B (as j), C (as j), and D (as i). This is the most complex. Vertex[2] -> B. In node B, vertex_j=2, so next_j points to node C. In node C, vertex_j=2, so its next_j points to node D. In node D, vertex_i=2, so its next_i is set to NULL.
• Vertex 3's List: Involved only in edge D (as j). Vertex[3] -> D. In node D, vertex_j=3, so its next_j is NULL.

To traverse all edges incident to Vertex 2, you start at Vertex[2] (pointing to node B). You see node B connects vertices (0,2). Since you came from Vertex 2, you check: is vertex_i==2? No (it's 0). Is vertex_j==2? Yes. Therefore, the next node in Vertex 2's list is found via next_j, which points to node C. You continue this process, using the appropriate next pointer based on which endpoint matches the vertex you're traversing.

Analyzing Memory and Algorithmic Efficiency

The primary advantage of the adjacency multilist is its memory efficiency for edge-centric operations. A standard adjacency list uses $2E$ neighbor references. The multilist uses $E$ edge nodes, each with two vertex endpoints and two next pointers. If we assume a vertex ID and a pointer are the same size, the memory for both structures is similar in big-O terms: $O(V+E)$. However, the multilist's practical overhead is often slightly higher per edge due to the larger node structure, but it provides a unified edge object.

The real gain is in algorithmic efficiency for operations that process edges. Consider an algorithm that must mark each edge as it is processed, like DFS to detect cycles in an undirected graph. In an adjacency list, marking the edge (u,v) requires searching and updating nodes in both vertex u's and vertex v's lists—an $O(degree(u)+degree(v))$ operation that can be costly. In a multilist, you mark the single shared edge node in constant time $O(1)$ once you have a reference to it. This simplifies logic and can improve performance for dense graphs or algorithms that frequently query edge states.

Adapting Graph Algorithms for Multilist

Implementing common graph algorithms with an adjacency multilist requires careful adaptation of traversal logic. The core change is in how you iterate over a vertex's neighbors. You cannot simply read a neighbor's ID; you must extract it from the edge node.

For Depth-First Search (DFS), the recursive function for a vertex v would work like this:

1. Mark vertex v as visited.
2. Get the first edge node from Vertex[v].
3. For the current edge node, determine the "other" vertex w that is not v.
4. If w is not visited, recursively call DFS on w. Critically, you can now mark this edge as traversed in the node itself.
5. To move to the next edge for vertex v, you must follow the correct next pointer (next_i if v == vertex_i, else next_j).

This adaptation centralizes edge management. Algorithms for finding connected components or detecting cycles become cleaner, as the edge state (used/unused) is stored once. However, algorithms that primarily ask "are vertices u and v adjacent?" may be slightly slower, as they may require a traversal of one vertex's edge list to find the shared node, whereas a standard adjacency list could use a hash set for constant-time adjacency checks.

Common Pitfalls

1. Incorrect Pointer Navigation During Traversal: The most frequent error is following the wrong next pointer when iterating through a vertex's edge list. You must check whether the current vertex matches vertex_i or vertex_j in the node to decide whether to use next_i or next_j to find the next edge in this vertex's specific chain.

• Correction: Always use a helper function getNextPointer(node, currentVertex) that returns node->next_i if currentVertex == node->vertex_i, else returns node->next_j.

1. Forgetting to Handle Both Endpoints in Edge Operations: When inserting a new edge, you must correctly thread it into the adjacency lists of both vertices. It's easy to correctly link it for one vertex but neglect to set the appropriate next pointer for the other endpoint's chain.

• Correction: Treat edge insertion as two separate list insertion operations: one into vertex $u$'s list and one into vertex $v$'s list. Verify the connections from both vertex array heads.

1. Misidentifying the "Other" Vertex: When processing an edge node from vertex $v$'s perspective, extracting the neighbor requires checking which field contains $v$.

• Correction: Use a clear conditional: neighbor = (node->vertex_i == v) ? node->vertex_j : node->vertex_i. Avoid assuming $v$ is always in vertex_i.

1. Increased Complexity for Directed Graphs: The basic multilist design is best for undirected graphs. Adapting it for directed graphs requires careful interpretation of the next_i and next_j pointers (e.g., as next_out and next_in), which adds conceptual complexity often outweighing the benefits.

• Correction: Reserve the standard adjacency multilist for undirected graphs. For directed graphs, consider if the edge-marking benefit justifies the more complex implementation, or stick with a standard adjacency list.

Summary

• The adjacency multilist stores each graph edge in a single node that is referenced from the adjacency lists of both its endpoint vertices, eliminating the data duplication present in a standard adjacency list.
• Its core advantage is efficient, $O(1)$ edge marking and deletion, as an edge is a unified object, making it superior for algorithms like DFS or Minimum Spanning Tree that need to track edge states.
• Memory usage is comparable to an adjacency list in big-O terms $O(V+E)$, but with a different trade-off: fewer edge objects but larger node structures.
• Implementing graph algorithms requires adapting traversal logic to correctly navigate the dual next_i and next_j pointers and to extract neighbor information from the shared edge nodes.
• This representation is a powerful tool in your data structure toolkit, exemplifying how tailoring the underlying model to the specific operations of an algorithm can yield significant efficiency gains.