Graph Basics: BFS, DFS, and Modeling

Graphs represent entities (nodes) and relationships (edges). They are used in maps, social networks, recommendation systems, and dependency graphs.

How to model a graph

Graphs represent entities (nodes) and relationships (edges). They are used in maps, social networks, recommendation systems, and dependency graphs.

Adjacency list is memory efficient for sparse graphs.
BFS finds shortest path in unweighted graphs.
DFS is useful for connectivity and cycle checks.

BFS shortest distance

Distance from source in unweighted graph

function bfsDistance(graph: Record<string, string[]>, start: string): Record<string, number> {
  const distance: Record<string, number> = { [start]: 0 };
  const queue: string[] = [start];

  while (queue.length) {
    const node = queue.shift()!;
    for (const next of graph[node] ?? []) {
      if (distance[next] !== undefined) continue;
      distance[next] = distance[node] + 1;
      queue.push(next);
    }
  }

  return distance;
}