Adjacency List in Graph Theory

---

In graph theory, an Adjacency List is another way to represent a graph, which is more space-efficient compared to the Adjacency Matrix for sparse graphs. Instead of using a 2D array, an adjacency list uses an array (or a list) of lists (or linked lists) to represent the connections between vertices. Each vertex in the graph has a list of adjacent vertices to which it is connected. This structure is particularly useful when the graph is sparse, meaning that the number of edges is much less than the square of the number of vertices.

---

What is an Adjacency List?

An Adjacency List is a data structure used to represent a graph. It consists of an array of lists, where each index of the array represents a vertex in the graph. The list at each index contains the vertices that are adjacent (connected) to the corresponding vertex.

In simpler terms, for a graph with $V$ vertices, we create an array of $V$ elements. Each element is a list (or linked list) containing the vertices that are directly connected by an edge.

Adjacency List for an Undirected Graph

In an undirected graph, if there is an edge between two vertices $u$ and $v$, both $u$ will include $v$ in its adjacency list, and $v$ will include $u$ in its list.

Example:

Consider the undirected graph:

    A - B
    |   |
    C - D

• Vertices: $A,B,C,D$
• Edges: $(A,B),(A,C),(B,D),(C,D)$

The adjacency list for this graph will look like this:

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Here, vertex $A$ is connected to vertices $B$ and $C$, so the adjacency list of $A$ contains $B$ and $C$. Similarly, the other vertices have their respective connections.

Adjacency List for a Directed Graph

In a directed graph, the adjacency list contains the vertices that are reachable by a directed edge from a given vertex. If there is an edge from vertex $u$ to vertex $v$, then $u$’s adjacency list will contain $v$, but $v$’s adjacency list will not contain $u$.

Example:

Consider the directed graph:

    A → B
    ↓   ↑
    C → D

• Vertices: $A,B,C,D$
• Edges: $(A,B),(A,C),(B,D),(C,D)$

The adjacency list for this directed graph would look like this:

A: [B, C]
B: [D]
C: [D]
D: []

Here, vertex $A$ has directed edges to $B$ and $C$, so its adjacency list contains $B$ and $C$. Vertex $B$ has a directed edge to $D$, so its list contains $D$, and so on.

---

Advantages of Adjacency List

1. Space Efficiency: For sparse graphs, an adjacency list uses less space compared to an adjacency matrix. The space complexity is $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges, which is much more efficient when the graph is sparse.

2. Faster Edge Enumeration: Enumerating the neighbors of a vertex is faster, requiring $O(k)$ time, where $k$ is the number of neighbors. This is more efficient than the adjacency matrix, where you have to scan an entire row.

3. Dynamic Graph Representation: It is easier to add or remove edges dynamically, as only the corresponding adjacency lists need to be updated.

4. Efficient for Sparse Graphs: The adjacency list is ideal for sparse graphs where the number of edges $E$ is much smaller than $V^2$, as it avoids using unnecessary space to store non-existent edges.

---

Disadvantages of Adjacency List

1. Slower Edge Lookup: To check if an edge exists between two vertices, you may need to scan through the adjacency list of the vertex, which takes $O(k)$ time, where $k$ is the number of neighbors of the vertex.

2. More Complex for Matrix Operations: Operations like matrix multiplication are less straightforward with adjacency lists compared to adjacency matrices.

---

Operations on Adjacency List

1. Check if an Edge Exists: To check if there is an edge between vertex $u$ and vertex $v$, you need to scan the adjacency list of vertex $u$ to see if $v$ is present. This operation takes $O(k)$ time, where $k$ is the number of neighbors of vertex $u$.

2. Add an Edge: To add an edge from vertex $u$ to vertex $v$, simply add $v$ to the adjacency list of $u$. This operation takes $O(1)$ time.

3. Remove an Edge: To remove an edge, you need to remove $v$ from the adjacency list of vertex $u$. This can take $O(k)$ time in the worst case if $v$ is at the end of the list.

4. Get All Neighbors of a Vertex: To get all neighbors of vertex $u$, you simply access the adjacency list of $u$, which takes $O(k)$ time.

---

Adjacency List in Python

Here's an example implementation of an Adjacency List in Python for both directed and undirected graphs:

class Graph:
    def __init__(self, vertices, directed=True):
        self.V = vertices  # Number of vertices
        self.graph = [[] for _ in range(vertices)]  # Initialize the adjacency list
        self.directed = directed

    def add_edge(self, u, v):
        # Add edge from u to v
        self.graph[u].append(v)
        if not self.directed:
            # For undirected graph, add edge from v to u as well
            self.graph[v].append(u)

    def remove_edge(self, u, v):
        # Remove edge from u to v
        if v in self.graph[u]:
            self.graph[u].remove(v)
        if not self.directed and u in self.graph[v]:
            # For undirected graph, remove edge from v to u as well
            self.graph[v].remove(u)

    def display(self):
        for i in range(self.V):
            print(f"Vertex {i}: {self.graph[i]}")

# Example usage for Directed Graph
g = Graph(4, directed=True)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print("Adjacency List for Directed Graph:")
g.display()

# Example usage for Undirected Graph
g2 = Graph(4, directed=False)
g2.add_edge(0, 1)
g2.add_edge(0, 2)
g2.add_edge(1, 3)
g2.add_edge(2, 3)

print("\nAdjacency List for Undirected Graph:")
g2.display()

Output:

Adjacency List for Directed Graph:
Vertex 0: [1, 2]
Vertex 1: [3]
Vertex 2: [3]
Vertex 3: []

Adjacency List for Undirected Graph:
Vertex 0: [1, 2]
Vertex 1: [0, 3]
Vertex 2: [0, 3]
Vertex 3: [1, 2]

 

---

---