DSA Basics: Graphs

A graph is a set of nodes connected by edges.

Graphs are useful when relationships matter more than order. Social networks, maps, dependency graphs, and recommendation systems can all be modeled as graphs.

Terms

• Vertex or node: one item in the graph.
• Edge: a connection between two nodes.
• Directed graph: edges have direction.
• Undirected graph: edges work both ways.
• Weighted graph: edges have costs.

Adjacency list

An adjacency list stores each node with the nodes connected to it.

const graph = {
	A: ['B', 'C'],
	B: ['A', 'D'],
	C: ['A'],
	D: ['B'],
};

Breadth-first search

BFS explores neighbors level by level and uses a queue.

function bfs(graph, start) {
	const visited = new Set([start]);
	const queue = [start];

	while (queue.length > 0) {
		const node = queue.shift();
		console.log(node);

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

Depth-first search

DFS goes deep before backtracking. It can be written with recursion or a stack.

Practice problems

1. Count connected components.
2. Find if a path exists.
3. Clone a graph.
4. Find shortest path in an unweighted graph.
5. Detect a cycle.

Practice links

• LeetCode Graph problems
• NeetCode practice roadmap