Graph Theory: Adjacency Matrix vs List & BFS vs DFS Traversals0%

Cycle Detection & Topological Sorting (Kahn's BFS & DFS)

Graph Theory: Adjacency Matrix vs List & BFS vs DFS Traversals

Beginner12 min read•Updated: Jul 11, 2026

Graph Theory: Adjacency Matrix vs List & BFS vs DFS Traversals

A Graph is a non-linear data structure consisting of a finite set of vertices (or nodes) $V$ and a collection of edges $E$ that connect pairs of vertices: $G = (V, E)$. Graphs generalize trees by eliminating the constraints of root nodes, parent-child hierarchies, and cycle-free requirements. Graphs model networks everywhere: social networks (friendships), city road systems, internet web pages (hyperlinks), and dependency packaging systems.

1. Graph Classifications & Terminology

Before writing code, we categorize graphs according to direction, weighting, and cyclic nature:

1
Directed (Digraph) vs. Undirected:

Undirected: If an edge exists between node $A$ and node $B$, you can travel bidirectionally: $(A, B) = (B, A)$.
Directed: Edges have orientation (arrows). $(A \to B)$ allows movement only from $A$ to $B$.

1
Weighted vs. Unweighted:

Unweighted: Every edge has uniform cost (effectively $1$).
Weighted: Edges carry numerical values representing distance, latency, toll fee, or capacity.

1
Cyclic vs. Acyclic:

Cyclic: Contains at least one closed walk starting and ending at the same vertex.
Acyclic (DAG): Directed Acyclic Graph contains zero directed cycles (essential for scheduling, Git commits, and compilers).

1
Degree:

In undirected graphs, degree is the number of incident edges.
In directed graphs, In-Degree is the count of incoming edges; Out-Degree is the count of outgoing edges.

2. Graph Representations: Matrix vs. List

Output

1Graph:
  (0) ----- (1)
   |       / |
   |     /   |
   |   /     |
  (2) ----- (3)
7 
Adjacency Matrix (4x4 Grid):
     0  1  2  3
  0 [0, 1, 1, 0]
  1 [1, 0, 1, 1]
  2 [1, 1, 0, 1]
  3 [0, 1, 1, 0]
  Space: O(V^2)
15 
Adjacency List (Hash Map or Array of Lists):
  0: [1, 2]
  1: [0, 2, 3]
  2: [0, 1, 3]
  3: [1, 2]
  Space: O(V + E)

Representation Trade-Off Matrix

Operation / Metric	Adjacency Matrix	Adjacency List (Standard)	Winner
Space Complexity	$O(V^2)$ regardless of edge count	$O(V + E)$ (or $O(V + 2E)$ for undirected)	List for sparse graphs
Add Vertex	$O(V^2)$ (reallocate matrix)	$O(1)$	List
Add Edge	$O(1)$	$O(1)$	Tie
Query Edge (u, v)	$O(1)$ (`matrix[u][v] == 1`)	$O(\text{deg}(u))$ (search list)	Matrix
Iterate Neighbors of u	$O(V)$ (scan entire row)	$O(\text{deg}(u))$ (scan only actual neighbors)	List

In technical interviews and real-world software, graphs are overwhelmingly sparse ($E \ll V^2$), making the Adjacency List the universal industry choice.

3. Graph Traversal: BFS vs. DFS

Traversing a graph requires exploring all reachable vertices while maintaining a visited set to prevent infinite loops caused by cycles.

Breadth-First Search (BFS)

Data Structure: FIFO Queue (collections.deque).
Strategy: Layer-by-layer exploration (level order).
Core Property: Computes the shortest path in unweighted graphs (minimum edge count).

Depth-First Search (DFS)

Data Structure: LIFO Stack (or recursion call stack).
Strategy: Explore as deep as possible along each branch before backtracking.
Core Property: Natural for connectivity, maze solving, cycle detection, and topological sorting.

4. Step-by-Step Traversal Trace

Given an undirected graph with nodes 0, 1, 2, 3, 4 and edges: (0,1), (0,2), (1,3), (2,4). Starting at node 0:

BFS Step-by-Step Execution

Step	Current Node	Visited Set	Queue State (Front -> Back)	Action / Neighbors Added
Initial	-	`{0}`	`[0]`	Start at root `0`
1	`0`	`{0, 1, 2}`	`[1, 2]`	Dequeue `0`, add neighbors `1, 2`
2	`1`	`{0, 1, 2, 3}`	`[2, 3]`	Dequeue `1`, add neighbor `3`
3	`2`	`{0, 1, 2, 3, 4}`	`[3, 4]`	Dequeue `2`, add neighbor `4`
4	`3`	`{0, 1, 2, 3, 4}`	`[4]`	Dequeue `3`, no unvisited neighbors
5	`4`	`{0, 1, 2, 3, 4}`	`[]`	Dequeue `4`, no unvisited neighbors. Queue empty!

BFS Traversal Order: [0, 1, 2, 3, 4]

5. Dual-Language Implementation

Python 3 Implementation

Python

1from collections import deque, defaultdict
2from typing import List, Dict, Set
3 
4class Graph:
  def __init__(self, is_directed: bool = False):
      self.adj_list: Dict[int, List[int]] = defaultdict(list)
      self.is_directed = is_directed
8 
  def add_edge(self, u: int, v: int) -> None:
      self.adj_list[u].append(v)
      if not self.is_directed:
          self.adj_list[v].append(u)
13 
  def bfs(self, start: int) -> List[int]:
      # Layer-by-layer exploration using an explicit FIFO Queue
      visited: Set[int] = {start}
      queue: deque[int] = deque([start])
      traversal: List[int] = []
19 
      while queue:
          node = queue.popleft()
          traversal.append(node)
23 
          for neighbor in self.adj_list[node]:
              if neighbor not in visited:
                  visited.add(neighbor)
                  queue.append(neighbor)
28 
      return traversal
30 
  def dfs(self, start: int) -> List[int]:
      # Deep exploration using recursion (implicit call stack)
      visited: Set[int] = set()
      traversal: List[int] = []
35 
      def _dfs_helper(node: int) -> None:
          visited.add(node)
          traversal.append(node)
          for neighbor in self.adj_list[node]:
              if neighbor not in visited:
                  _dfs_helper(neighbor)
42 
      _dfs_helper(start)
      return traversal
45 
46# Example Usage
47if __name__ == "__main__":
  g = Graph(is_directed=False)
  edges = [(0, 1), (0, 2), (1, 3), (2, 4)]
  for u, v in edges:
      g.add_edge(u, v)
52 
  print("BFS Order:", g.bfs(0))  # [0, 1, 2, 3, 4]
  print("DFS Order:", g.dfs(0))  # [0, 1, 3, 2, 4]

Modern JavaScript (Node.js / ES6) Implementation

JavaScript

1class Graph {
constructor(isDirected = false) {
  this.adjList = new Map();
  this.isDirected = isDirected;
}
6 
addVertex(v) {
  if (!this.adjList.has(v)) {
    this.adjList.set(v, []);
  }
}
12 
addEdge(u, v) {
  this.addVertex(u);
  this.addVertex(v);
  this.adjList.get(u).push(v);
  if (!this.isDirected) {
    this.adjList.get(v).push(u);
  }
}
21 
bfs(start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
26 
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
30 
    const neighbors = this.adjList.get(node) || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}
41 
dfs(start) {
  const visited = new Set();
  const order = [];
45 
  const dfsRecursive = (node) => {
    visited.add(node);
    order.push(node);
49 
    const neighbors = this.adjList.get(node) || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfsRecursive(neighbor);
      }
    }
  };
57 
  dfsRecursive(start);
  return order;
}
61}
62 
63// Example Execution
64const g = new Graph(false);
65[[0, 1], [0, 2], [1, 3], [2, 4]].forEach(([u, v]) => g.addEdge(u, v));
66 
67console.log("BFS Order:", g.bfs(0)); // [0, 1, 2, 3, 4]
68console.log("DFS Order:", g.dfs(0)); // [0, 1, 3, 2, 4]

6. Complexity Analysis

Algorithm	Time Complexity	Space Complexity	Primary Best-Use Case
BFS (Adj List)	$O(V + E)$	$O(V)$	Finding unweighted shortest path; finding nodes within $k$ hops
DFS (Adj List)	$O(V + E)$	$O(V)$ (recursion depth)	Topological sort; backtracking; finding cycles; flood fill
BFS (Adj Matrix)	$O(V^2)$	$O(V)$	Dense graphs where $E \approx V^2$

Why $O(V + E)$? Every vertex is placed into the queue/stack at most once ($O(V)$). For each vertex, we iterate over all its incident edges ($O(E)$ total edges processed across all adjacency lists).

7. Common Pitfalls & Interview Traps

1
Disconnected Graphs / Forest: Calling BFS or DFS from a single starting node only visits that connected component. In problems like Number of Connected Components or Number of Islands, you must wrap BFS/DFS in an outer loop over all vertices: for node in range(V): if node not in visited: bfs(node).
2
Missing visited Check before Queueing: Adding nodes to the BFS queue without marking them visited immediately allows duplicates into the queue, causing catastrophic $O(2^V)$ exponential memory spikes!
3
Call Stack Overflow in DFS: Deep graph traversals (e.g., $10^5$ linear nodes) will crash Python with RecursionError. In production or deep graphs, convert DFS to an explicit stack loop.

Interactive Quiz• Knowledge Check

Multiple Choice Questions

Question 1

What is the primary advantage of representing a sparse graph using an Adjacency List instead of an Adjacency Matrix?

Question 2

Why is Breadth-First Search (BFS) guaranteed to find the shortest path between two nodes in an unweighted graph?

Question 3

If a graph has 10,000 vertices and 12,000 edges, what is the space complexity of an Adjacency Matrix vs. an Adjacency List?

Question 4

When implementing BFS on a graph, at which precise moment MUST a node be marked as visited?

Question 5

What is the time complexity of running Depth-First Search on a graph with $V$ vertices and $E$ edges represented by an adjacency list?

Next Lesson

Cycle Detection & Topological Sorting (Kahn's BFS & DFS)

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous Lesson	Next Lesson
Heaps & Priority Queues: Min-Heap, Max-Heap, Heapify & Top-K Elements	Cycle Detection & Topological Sorting (Kahn's BFS & DFS)

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

Previous Next

PreviousPrevNext