Graph Representation (Adjacency List)

An Adjacency List is the most common way to represent graphs in practice, especially for sparse graphs (where the number of edges is much less than $V^2$).

In this representation, we maintain an array (or map) of lists. The size of the array is equal to the number of vertices $V$. For each vertex $i$, the list at index $i$ contains all the vertices that are adjacent to $i$.

Adjacency List Concept

For the undirected graph shown below:

The corresponding Adjacency List representation is:

Index [0]  -->  1  -->  4  -->  /
Index [1]  -->  0  -->  4  -->  2  -->  3  -->  /
Index [2]  -->  1  -->  3  -->  /
Index [3]  -->  1  -->  4  -->  2  -->  /
Index [4]  -->  3  -->  0  -->  1  -->  /

(where / represents the end of the list/null)

JavaScript Implementation

Here is a complete JavaScript implementation of a graph using an Adjacency List:

class Graph {
    constructor() {
        this.list = {};
    }
    
    // Add a vertex/node to the graph
    addVertex(vertex) {
        if (!this.list[vertex]) {
            this.list[vertex] = [];
        }
    }
    
    // Add an undirected edge between vertex1 and vertex2
    addEdge(vertex1, vertex2) {
        // Ensure both vertices exist
        this.addVertex(vertex1);
        this.addVertex(vertex2);
        
        this.list[vertex1].push(vertex2);
        this.list[vertex2].push(vertex1);
    }
    
    // Display the adjacency list connections
    showConnections() {
        Object.keys(this.list).forEach(vertex => {
            console.log(`${vertex} --> ${this.list[vertex].join(", ")}`);
        });
    }
}
 
// Example usage:
const g = new Graph();
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
 
g.showConnections();
/*
Output:
A --> B, C
B --> A, D
C --> A, E
D --> B
E --> C
*/

Complexity Analysis

• Space Complexity: $O(V + E)$ (or $O(V + 2E)$ for undirected graphs)
• Adding a vertex: $O(1)$
• Adding an edge: $O(1)$
• Removing a vertex: $O(V + E)$ (must remove the vertex and search all lists to clean up edges pointing to it)
• Removing an edge: $O(V)$ (requires searching the adjacency list of the vertex to remove the edge)
• Querying edge existence (u -> v): $O(V)$ (worst case, if a vertex is connected to all other vertices)

Advantages and Disadvantages

Advantages

• Highly Space-Efficient: Saves a massive amount of memory for sparse graphs compared to an Adjacency Matrix.
• Fast Vertex Insertion: Adding a new vertex is a constant time operation $O(1)$.
• Iterating Neighbors: Finding all neighbors of a vertex is extremely fast and takes optimal time proportional to the degree of the vertex.

Disadvantages

• Slower Edge Queries: Checking if there is an edge between vertex u and v takes $O(V)$ in the worst case (compared to $O(1)$ in an Adjacency Matrix), as we must traverse the list of neighbors for u.