Graphs

Why Graphs?

Graphs model relationships. Social networks (who follows whom), maps (roads between cities), dependency trees (build order), web pages (links) — all graphs. If your problem involves connections between things, you’re dealing with a graph.

Representing Graphs

// Adjacency list — most common, space-efficient
type Graph = Map<string, string[]>;

function buildGraph(edges: [string, string][]): Graph {
	const graph: Graph = new Map();

	for (const [from, to] of edges) {
		if (!graph.has(from)) graph.set(from, []);
		if (!graph.has(to)) graph.set(to, []);
		graph.get(from)!.push(to);
		graph.get(to)!.push(from); // omit for directed graph
	}
	return graph;
}

DFS and BFS on Graphs

// DFS — go deep, then backtrack
function dfs(graph: Graph, start: string): string[] {
	const visited = new Set<string>();
	const result: string[] = [];

	function visit(node: string) {
		if (visited.has(node)) return;
		visited.add(node);
		result.push(node);
		for (const neighbor of graph.get(node) || []) {
			visit(neighbor);
		}
	}

	visit(start);
	return result;
}

// BFS — explore level by level
function bfs(graph: Graph, start: string): string[] {
	const visited = new Set<string>([start]);
	const queue: string[] = [start];
	const result: string[] = [];

	while (queue.length) {
		const node = queue.shift()!;
		result.push(node);

		for (const neighbor of graph.get(node) || []) {
			if (!visited.has(neighbor)) {
				visited.add(neighbor);
				queue.push(neighbor);
			}
		}
	}
	return result;
}

Topological Sort

Order nodes so that every directed edge goes from earlier to later. Used for build systems, course prerequisites, task scheduling.

function topologicalSort(graph: Map<string, string[]>): string[] {
	const visited = new Set<string>();
	const result: string[] = [];

	function dfs(node: string) {
		if (visited.has(node)) return;
		visited.add(node);
		for (const neighbor of graph.get(node) || []) {
			dfs(neighbor);
		}
		result.push(node); // add after all dependencies
	}

	for (const node of graph.keys()) {
		dfs(node);
	}

	return result.reverse();
}

Key Takeaways

1. Adjacency lists are the go-to representation — space-efficient and easy to traverse
2. Always track visited nodes to avoid infinite loops in graphs with cycles
3. BFS finds shortest paths in unweighted graphs; DFS explores all paths
4. Topological sort is essential for dependency resolution