Adjacency List

Problem

{
    0: [1, 3, 2],
    1: [0, 2],
    2: [1, 3, 0],
    3: [2, 0]
}

An adjacency list is a common way to represent a graph. In an adjacency list, we are given a list of nodes, where each node is mapped to a list of its neighbors.

In Python, we can create an adjacency list using a dictionary where the keys are the nodes and the values are the list of nodes each node is connected to.

adjList = {
        1: [2],
        2: [1, 3, 4],
        3: [2, 4],
        4: [2, 3, 5],
        5: [4]
    }

Adjacency lists allow you to look up the neighbors of any node in O(1) time, which is a necessary step for depth-first search.

Constructing Adjacency Lists

Some questions require you to build an adjacency list from a list of edges, which is shown below:

Solution

def build_adj_list(n, edges):
    adj_list = {i: [] for i in range(n)}

    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)
        
    return adj_list

public static Map<Integer, List<Integer>> buildAdjList(int n, int[][] edges) {
    Map<Integer, List<Integer>> adjList = new HashMap<>();
    
    for (int i = 0; i < n; i++) {
        adjList.put(i, new ArrayList<>());
    }

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }
        
    return adjList;
}

func buildAdjList(n int, edges [][]int) map[int][]int {
    adjList := make(map[int][]int)
    
    for i := 0; i < n; i++ {
        adjList[i] = []int{}
    }

    for _, edge := range edges {
        u := edge[0]
        v := edge[1]
        adjList[u] = append(adjList[u], v)
        adjList[v] = append(adjList[v], u)
    }
        
    return adjList
}

function buildAdjList(n: number, edges: number[][]): { [key: number]: number[] } {
    const adjList: { [key: number]: number[] } = {};
    
    for (let i = 0; i < n; i++) {
        adjList[i] = [];
    }

    for (const [u, v] of edges) {
        adjList[u].push(v);
        adjList[v].push(u);
    }
        
    return adjList;
}

DFS on an Adjacency List

DFS for a graph is conceptually similar to DFS on a binary tree. The algorithm tries to go as deep as possible along a path before backtracking to explore other paths.

The key differences are:

Each node can have any amount of neighbors, so we need a for loop to iterate over each neighbor rather than making calls to the left and right children of the current node.
Because graphs can contain cycles, we need to keep track of nodes we have already visited. If we encounter a node that has already been visited, we should return immediately without making any further recursive calls (or skip it in the loop altogether). Otherwise, we may end up in an infinite loop.
We don’t need an explicit base case like we do in the trees. Eventually, we will visit all nodes in the graph, and the recursion will stop on its own (with the help of the visited set).

Here’s a basic implementation of DFS on an adjacency list. Notice how we use a visited set to keep track of the nodes we have visited, and how we return immediately if we encounter a node that has already been visited.

adjList = {
    "1": ["2", "4"],
    "2": ["1", "3"],
    "3": ["2", "4"],
    "4": ["1", "3", "5"],
    "5": ["4"]
}

def dfs(adjList):
  if not adjList:
    return
  visited = set()

  def dfs_helper(node):
    if node in visited:
      return

    visited.add(node)
    for neighbor in adjList[node]:
      dfs_helper(neighbor)
    return

  # Handle disconnected components
  for node in adjList:
    if node not in visited:
      dfs_helper(node)

import java.util.*;

public void dfs(Map<Integer, List<Integer>> adjList) {
    if (adjList == null || adjList.isEmpty()) {
        return;
    }
    Set<Integer> visited = new HashSet<>();

    void dfsHelper(int node) {
        if (visited.contains(node)) {
            return;
        }

        visited.add(node);
        for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
            dfsHelper(neighbor);
        }
        return;
    }

    // Handle disconnected components
    for (int node : adjList.keySet()) {
        if (!visited.contains(node)) {
            dfsHelper(node);
        }
    }
}

func dfs(adjList map[int][]int) {
    if len(adjList) == 0 {
        return
    }
    visited := make(map[int]bool)

    var dfsHelper func(int)
    dfsHelper = func(node int) {
        if visited[node] {
            return
        }

        visited[node] = true
        for _, neighbor := range adjList[node] {
            dfsHelper(neighbor)
        }
        return
    }

    // Handle disconnected components
    for node := range adjList {
        if !visited[node] {
            dfsHelper(node)
        }
    }
}

function dfs(adjList: { [key: number]: number[] }): void {
  if (!adjList || Object.keys(adjList).length === 0) {
    return;
  }
  const visited = new Set<number>();

  function dfsHelper(node: number): void {
    if (visited.has(node)) {
      return;
    }

    visited.add(node);
    for (const neighbor of adjList[node] || []) {
      dfsHelper(neighbor);
    }
    return;
  }

  // Handle disconnected components
  for (const node in adjList) {
    if (!visited.has(parseInt(node))) {
      dfsHelper(parseInt(node));
    }
  }
}

Summary

Use a set to keep track of visited nodes. Each time you visit a node, add it to the set.
If you encounter a node that has already been visited, return immediately without making any further recursive calls.
Use a for loop to iterate over each neighbor of the current node, and recursively call dfs on each neighbor.

The next step is to practice using DFS to solve graph questions involving adjacency lists.