Adjacency List

An adjacency list is a way of representing a graph as a collection of lists. Each vertex in the graph has a corresponding list containing the vertices that are adjacent to it.

In contrast to an adjacency matrix, only the existing edges are stored. This saves space and avoids storing empty relationships.

Adjacency lists are efficient for sparse graphs with limited edges between vertices. Lookup and storage is more efficient compared to adjacency matrix.

Solution

Here is an implementation of adjacency list in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class AdjacencyList:

  def __init__(self):
    self.vertices = {}
  
  def addVertex(self, vertex):
    self.vertices[vertex] = []
  
  def addEdge(self, fromVertex, toVertex):
    self.vertices[fromVertex].append(toVertex)

g = AdjacencyList()
g.addVertex(1)
g.addVertex(2)
g.addEdge(1, 2)
print(g.vertices)

# {1: [2], 2: []} 

Key aspects:

Use a dictionary to represent the graph
Map each vertex to a list of its adjacent vertices
Add edges by appending to the adjacency list

This provides an efficient representation by avoiding storage of non-edges. Lookup and search is also faster with linked lists.

Adjacency lists are commonly used due to these advantages over adjacency matrix.

Description: Adjacency List

An Adjacency List is a collection of lists or arrays that represents a graph. In an Adjacency List, each vertex of the graph is associated with a list or array containing its neighboring vertices. This representation is space-efficient for sparse graphs, where the number of edges is far less than the number of vertices squared. It is also efficient in terms of time complexity for algorithms that explore a graph vertex by vertex.

Solution:

Below, we demonstrate how to implement an undirected graph using an adjacency list in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.LinkedList;

public class AdjacencyList {
    private LinkedList<Integer>[] adjList;

    public AdjacencyList(int vertices) {
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; ++i) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int src, int dest) {
        adjList[src].add(dest);
        adjList[dest].add(src);
    }

    public void printGraph() {
        for (int i = 0; i < adjList.length; ++i) {
            System.out.print(i);
            for (int x : adjList[i]) {
                System.out.print(" -> " + x);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyList graph = new AdjacencyList(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 3);
        graph.addEdge(3, 4);
        graph.addEdge(1, 2);

        graph.printGraph();
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <list>

class AdjacencyList {
private:
    std::vector<std::list<int>> adjList;

public:
    AdjacencyList(int vertices) {
        adjList.resize(vertices);
    }

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);
    }

    void printGraph() {
        for (int i = 0; i < adjList.size(); ++i) {
            std::cout << i;
            for (auto x : adjList[i]) {
                std::cout << " -> " << x;
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    AdjacencyList graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 3);
    graph.addEdge(3, 4);
    graph.addEdge(1, 2);

    graph.printGraph();
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class AdjacencyList:
    def __init__(self, vertices):
        self.adjList = [[] for _ in range(vertices)]

    def addEdge(self, src, dest):
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

    def printGraph(self):
        for i, adj in enumerate(self.adjList):
            print(i, end="")
            for x in adj:
                print(" ->", x, end="")
            print()

if __name__ == "__main__":
    graph = AdjacencyList(5)
    graph.addEdge(0, 1)
    graph.addEdge(0, 4)
    graph.addEdge(1, 3)
    graph.addEdge(3, 4)
    graph.addEdge(1, 2)

    graph.printGraph()

Key Takeaways

Adjacency List is a widely-used graph representation that is efficient in both space and time complexity for many algorithms.
You can easily add or remove edges and query connections between vertices.
Java uses LinkedList to represent the list of adjacent vertices, while C++ uses std::list and Python uses native lists.