Graphs Overview
Introduction to Graphs and adapting DFS for cycles.
Examples
The components are {0, 1, 2} and {3, 4}.
One chain connects all five nodes.
What is a Graph?
A Graph is a non-linear data structure consisting of vertices (nodes) and edges (lines connecting nodes). Unlike trees, graphs have no strict hierarchy: any node can be connected to any other node.
Key Terminology
- Vertex (Node): The fundamental unit (e.g., a City, User, Webpage).
- Edge: The connection between two vertices (e.g., Road, Follow, Hyperlink).
- Degree: The number of edges connected to a vertex. In directed graphs, this splits into in-degree (incoming) and out-degree (outgoing).
- Path: A sequence of edges connecting a sequence of vertices.
Real-World Examples
- Social Networks: Users are nodes, friendships are edges.
- Google Maps: Intersections are nodes, roads are edges.
- The Internet: Webpages are nodes, hyperlinks are edges.
Types of Graphs
Key distinctions you must know:
Directed (DiGraph): Edges have a direction (A → B). Moving from A to B is allowed, but B to A is not (unless a separate edge exists). e.g., Twitter followers.
Undirected: Edges are bidirectional (A - B). e.g., Facebook friends.
Weighted: Edges have values (weights) assigned to them. e.g., Flight costs between cities.
Cyclic vs Acyclic: A cyclic graph contains at least one path that starts and ends at the same node using different edges.
Connected vs Disconnected: In a connected graph, there is a path between every pair of vertices. Disconnected graphs have isolated sub-graphs (islands).
Graph Representations
How do we store a graph in code? There are two primary ways:
Adjacency Matrix: A 2D array where
grid[i][j] = 1if there is an edge fromitoj.- Pros: O(1) edge lookup.
- Cons: O(V²) space, even if the graph is sparse.
Adjacency List (Most Common): A Map or Array of Lists where each key is a node and the value is a list of its neighbors.
- Pros: O(V + E) space. Efficient for sparse graphs.
- Cons: O(Degree) to check if a specific edge exists.
We will focus primarily on the Adjacency List as it is the most common representation in technical interviews.
DFS on Graphs: The 'Visited' Set
DFS on a graph works just like on a tree: we explore as deep as possible before backtracking. However, there is one critical difference:
Cycles and Revisited Nodes
In a tree, we always move down from parent to child, guaranteeing we never visit the same node twice. In a graph, edges can point anywhere. A node can point back to its ancestor (cycle) or two nodes can point to the same neighbor.
Without tracking where we've been, our DFS would recurse infinitely in a cycle (A → B → A → ...).
The Solution: The visited Set
We strictly enforce a rule: "Never process a node more than once."
We maintain a HashSet (or boolean array) called visited.
- Before traversing to a neighbor, check if it's in
visited. - If yes, skip it.
- If no, mark it as visited and recurse.
Handling Disconnected Graphs
A single DFS from node 0 only reaches node 0's own piece of the graph. If the graph is disconnected, the other pieces — its connected components — are never touched.
So the DFS goes inside a loop over every node. A node that is still unvisited was not reached by any earlier DFS, so it starts a new component:
components = 0
for node in range(n):
if not visited[node]:
components += 1
dfs(node)
Each DFS started from this loop marks exactly one whole component, so counting the starts counts the components.
DFS Graph Visualization
Count the connected components of n nodes and a list of edges (LeetCode 323). The outer loop tries every node; each one still unvisited starts a new DFS, and every node that DFS reaches gets the same component number. Watch the skips: a node already visited is never explored again, which is what stops the walk from going round a cycle forever.
Edge Cases & Common Mistakes
Watch out for these scenarios in interviews:
Infinite Loops: Forgetting the
visitedset will cause a Stack Overflow on cyclic graphs.Disconnected Graphs: Assuming the graph is fully connected and only calling DFS on node 0. You must iterate through all nodes.
No Edges: LeetCode guarantees
n ≥ 1, butedgescan be empty. Then every node is its own component and the answer isn.Self-Loops: A node with an edge to itself (A → A). The visited set logic handles this naturally, but be aware of it.
Directed vs Undirected: Treating a directed edge as undirected or vice-versa is a common bug.
Code: Count Connected Components
The template on a real problem, LeetCode 323 (Number of Connected Components in an Undirected Graph): build the adjacency list, keep a visited array, and start a DFS from every node that is still unvisited.
Note: LeetCode 323 is a Premium problem. LeetCode 547, Number of Provinces, is free and asks the same question with the graph given as an adjacency matrix instead of an edge list.
Graphs Overview Code
1var countComponents = function(n, edges) {2 const graph = Array.from({ length: n }, () => []);3 for (const [a, b] of edges) {4 graph[a].push(b);5 graph[b].push(a);6 }78 const visited = new Array(n).fill(false);910 function dfs(node) {11 visited[node] = true;12 for (const neighbor of graph[node]) {13 if (!visited[neighbor]) {14 dfs(neighbor);15 }16 }17 }1819 let components = 0;20 for (let node = 0; node < n; node++) {21 if (!visited[node]) {22 components++;23 dfs(node);24 }25 }26 return components;27};
Summary
Graph DFS is nearly identical to Tree DFS, but requires a visited set to prevent cycles and redundant work. Always verify if the graph is directed/undirected and connected/disconnected.