Implement a Graph using Adjacency List

An adjacency list is a common way to represent a graph by storing for each vertex, the list of vertices it is adjacent to. This allows efficient representation for sparse graphs.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Graph {
  Map<Integer, List<Integer>> adjList = new HashMap<>();

  void addEdge(int u, int v) {
    adjList.computeIfAbsent(u, x-> new ArrayList()).add(v);
    adjList.computeIfAbsent(v, x-> new ArrayList()).add(u); 
  }
  
  void printGraph() {
    for (Map.Entry<Integer, List<Integer>> entry: adjList.entrySet()) {
      int u = entry.getKey();
      List<Integer> neighbors = entry.getValue();
      System.out.println(u + "->" + neighbors); 
    }
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Graph {
  unordered_map<int, vector<int>> adjList;

public:
  void addEdge(int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u);
  }

  void printGraph() {
    for (auto it = adjList.begin(); it != adjList.end(); ++it) {
      int u = it->first;
      vector<int> neighbors = it->second;
      cout << u << "->" << neighbors << "\n";
    }
  }
};

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Graph:
  
  def __init__(self):
    self.adj_list = {}

  def add_edge(self, u, v):
    if u not in self.adj_list:
      self.adj_list[u] = []
    if v not in self.adj_list:
      self.adj_list[v] = []
      
    self.adj_list[u].append(v)
    self.adj_list[v].append(u)

  def print_graph(self):
    for u, neighbors in self.adj_list.items():
      print(u, '->', neighbors)

The adjacency list provides an efficient representation for sparse graphs compared to an adjacency matrix.

In graph theory, a graph consists of nodes (vertices) and edges. An adjacency list is one way to represent a graph. Each node has a list of nodes to which it is directly connected. This representation is efficient for sparse graphs where the number of edges is much less than the total possible edges (n*(n-1)/2 for undirected graphs). The primary operations involve adding vertices, adding edges, and traversing the graph.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import java.util.LinkedList;

class Graph {
    int vertices;
    LinkedList<Integer>[] adjList;

    Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

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

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <vector>
#include <list>
using namespace std;

class Graph {
private:
    int vertices;
    vector<list<int>> adjList;

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

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

Python

1
2
3
4
5
6
7
8
class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjList = [[] for _ in range(vertices)]

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

The examples in Java, C++, and Python use linked lists (Java), lists in STL (C++), and lists (Python) to store the adjacency list for each vertex. The addEdge function adds an edge by appending the destination vertex to the source vertex’s list and vice versa, assuming an undirected graph.