Graphs: Adjacency List Representation and Traversal

1. Adjacency List Overview

• Definition: A data structure representing a graph as a hash map (or dictionary) where each node (vertex) maps to a list of its neighbors.
  • Key: Unique node identifier (e.g., A, B).
  • Value: List of nodes directly reachable via edges.
• Use Case: Efficiently store sparse graphs (few edges relative to nodes).

Example

adj_list = {
    'A': ['B'],
    'B': ['C', 'E'],
    'C': ['E'],
    'E': ['D'],
    'D': []
}

Visual Representation:

A → B → C → E → D
    ↳ → → → ↑

2. Building an Adjacency List from Edges

Input: List of directed edges (e.g., [('A', 'B'), ('B', 'C'), ('B', 'E'), ('C', 'E'), ('E', 'D')]).

Steps:

1. Initialize an empty adjacency list (hash map).
2. For each edge (source, destination):
   • Add source to the adjacency list if not present.
   • Append destination to source's neighbor list.
   • Add destination to the adjacency list if not present (to include isolated nodes).

Code Implementation

def build_adjacency_list(edges):
    adj_list = {}
    for src, dest in edges:
        if src not in adj_list:
            adj_list[src] = []
        if dest not in adj_list:
            adj_list[dest] = []
        adj_list[src].append(dest)
    return adj_list

3. Depth-First Search (DFS) on Adjacency Lists

Objective: Count all paths from a start node to a target node.

Algorithm: