Kata: Graph Representation and Traversal

Table of contents

Problem Statement

Implement an undirected graph that supports:

• addVertex(vertex) — add a vertex
• addEdge(v1, v2) — add an undirected edge
• bfs(start) — breadth-first traversal, returning vertices in visit order
• dfs(start) — depth-first traversal, returning vertices in visit order
• hasPath(start, end) — check if a path exists between two vertices

Concepts

A graph is a collection of vertices (nodes) connected by edges. The adjacency list representation stores each vertex’s neighbors in a list, providing space-efficient storage for sparse graphs.

• BFS uses a queue — explores all neighbors before going deeper (level by level)
• DFS uses a stack (or recursion) — explores as deep as possible before backtracking

TypeScript: Uses Map<string, string[]> for the adjacency list. See TypeScript Core Concepts.

Python: defaultdict(list) is ideal for adjacency lists. See Python Core Concepts.

Boilerplate

TypeScript

// graph.ts
class Graph {
  private adjacencyList: Map<string, string[]> = new Map();

  addVertex(vertex: string): void { /* TODO */ }
  addEdge(v1: string, v2: string): void { /* TODO */ }
  bfs(start: string): string[] { /* TODO */ return []; }
  dfs(start: string): string[] { /* TODO */ return []; }
  hasPath(start: string, end: string): boolean { /* TODO */ return false; }
}

Python

# graph.py
from collections import defaultdict, deque

class Graph:
    def __init__(self) -> None:
        self._adj: defaultdict[str, list[str]] = defaultdict(list)

    def add_vertex(self, vertex: str) -> None: ...
    def add_edge(self, v1: str, v2: str) -> None: ...
    def bfs(self, start: str) -> list[str]: ...
    def dfs(self, start: str) -> list[str]: ...
    def has_path(self, start: str, end: str) -> bool: ...

Hints

Solution

TypeScript

class Graph {
  private adjacencyList: Map<string, string[]> = new Map();

  addVertex(vertex: string): void {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1: string, v2: string): void {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1)!.push(v2);
    this.adjacencyList.get(v2)!.push(v1);
  }

  bfs(start: string): string[] {
    const visited = new Set<string>();
    const result: string[] = [];
    const queue: string[] = [start];
    visited.add(start);

    while (queue.length > 0) {
      const vertex = queue.shift()!;
      result.push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex) ?? []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return result;
  }

  dfs(start: string): string[] {
    const visited = new Set<string>();
    const result: string[] = [];
    const stack: string[] = [start];

    while (stack.length > 0) {
      const vertex = stack.pop()!;
      if (visited.has(vertex)) continue;

      visited.add(vertex);
      result.push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex) ?? []) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }

    return result;
  }

  hasPath(start: string, end: string): boolean {
    const visited = new Set<string>();
    const queue: string[] = [start];
    visited.add(start);

    while (queue.length > 0) {
      const vertex = queue.shift()!;
      if (vertex === end) return true;

      for (const neighbor of this.adjacencyList.get(vertex) ?? []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return false;
  }
}

Python

from collections import defaultdict, deque

class Graph:
    def __init__(self) -> None:
        self._adj: defaultdict[str, list[str]] = defaultdict(list)

    def add_vertex(self, vertex: str) -> None:
        if vertex not in self._adj:
            self._adj[vertex] = []

    def add_edge(self, v1: str, v2: str) -> None:
        self._adj[v1].append(v2)
        self._adj[v2].append(v1)

    def bfs(self, start: str) -> list[str]:
        visited = {start}
        result: list[str] = []
        queue = deque([start])

        while queue:
            vertex = queue.popleft()
            result.append(vertex)

            for neighbor in self._adj[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        return result

    def dfs(self, start: str) -> list[str]:
        visited: set[str] = set()
        result: list[str] = []
        stack = [start]

        while stack:
            vertex = stack.pop()
            if vertex in visited:
                continue

            visited.add(vertex)
            result.append(vertex)

            for neighbor in self._adj[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

        return result

    def has_path(self, start: str, end: str) -> bool:
        visited = {start}
        queue = deque([start])

        while queue:
            vertex = queue.popleft()
            if vertex == end:
                return True
            for neighbor in self._adj[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        return False

Complexity Analysis

Where V = vertices, E = edges.

Cross-Language Notes

Python: The combination of defaultdict(list) and deque makes Python particularly elegant for graph algorithms. The set type provides O(1) membership testing for the visited set.

PHP: Use associative arrays (array<string, array<string>>) for adjacency lists. PHP’s SplQueue works well for BFS. See PHP Core Concepts.

Rust: The petgraph crate provides a comprehensive graph library with multiple representations and algorithms.

See also: Kata: Depth-First Search and Kata: Dijkstra’s Shortest Path for more advanced graph algorithms.