A graph consists of vertices (nodes) and edges connecting them. Graphs can be directed or undirected, weighted or unweighted.
Representations:
| Approach | Space | Check edge | Iterate neighbors |
|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(V) |
| Adjacency List | O(V + E) | O(degree) | O(degree) |
| Edge List | O(E) | O(E) | O(E) |
Adjacency list is the most common choice for interviews.
// Graph as adjacency list
var graph = new Dictionary<int, List<int>>();
// Build from edges
void BuildGraph(int[][] edges) {
foreach (var e in edges) {
int u = e[0], v = e[1];
if (!graph.ContainsKey(u)) graph[u] = new List<int>();
if (!graph.ContainsKey(v)) graph[v] = new List<int>();
graph[u].Add(v);
graph[v].Add(u); // undirected - add both directions
}
}
// Graph represented as List<int>[] (if vertices are 0..n-1)
int n = 6;
var graph2 = new List<int>[n];
for (int i = 0; i < n; i++) graph2[i] = new List<int>();
// Each edge: graph2[u].Add(v); graph2[v].Add(u);
// Weighted graph
var weighted = new Dictionary<int, List<(int neighbor, int weight)>>();
weighted[u].Add((v, 5));| BFS (Queue) | DFS (Stack/Recursion) | |
|---|---|---|
| Order | Level by level | Deep first |
| Shortest path | Yes (unweighted) | No |
| Space | O(width) | O(depth) |
| Use case | Shortest path, level order | Topological, connectivity, cycles |
Key difference: BFS uses a queue and explores neighbors level by level. DFS uses a stack (or recursion) and goes deep before backtracking.
Explore all nodes of this graph starting from node A, visiting each node exactly once.
// BFS - shortest path in unweighted graph
int Bfs(Dictionary<int, List<int>> graph, int start, int target) {
var q = new Queue<int>();
var visited = new HashSet<int>();
q.Enqueue(start);
visited.Add(start);
int distance = 0;
while (q.Count > 0) {
int size = q.Count;
for (int i = 0; i < size; i++) {
int node = q.Dequeue();
if (node == target) return distance;
foreach (var neighbor in graph.GetValueOrDefault(node, [])) {
if (visited.Add(neighbor))
q.Enqueue(neighbor);
}
}
distance++;
}
return -1; // not reachable
}
// DFS - recursive (for connectivity, cycle detection)
bool Dfs(Dictionary<int, List<int>> graph, int node, HashSet<int> visited) {
if (visited.Contains(node)) return false;
visited.Add(node);
foreach (var neighbor in graph.GetValueOrDefault(node, []))
Dfs(graph, neighbor, visited);
return true;
}A topological order of a directed acyclic graph (DAG) is an ordering where every edge goes from earlier to later nodes.
Applications: Course prerequisites, build dependencies, task scheduling.
Two algorithms:
int[] TopologicalSort(int n, int[][] edges) {
var graph = new List<int>[n];
var inDegree = new int[n];
for (int i = 0; i < n; i++) graph[i] = new List<int>();
foreach (var e in edges) {
graph[e[0]].Add(e[1]);
inDegree[e[1]]++;
}
var q = new Queue<int>();
for (int i = 0; i < n; i++)
if (inDegree[i] == 0) q.Enqueue(i);
var result = new List<int>();
while (q.Count > 0) {
int node = q.Dequeue();
result.Add(node);
foreach (var neighbor in graph[node]) {
if (--inDegree[neighbor] == 0)
q.Enqueue(neighbor);
}
}
return result.Count == n ? result.ToArray() : []; // [] if cycle
}A graph is the right abstraction when:
Graph vs other structures:
| Structure | Use when |
|---|---|
| Tree | Strict hierarchy (one parent per node) |
| Graph | Arbitrary connections (many-to-many) |
| Adjacency list | Most interview problems (space-efficient) |
| Adjacency matrix | Dense graph, need O(1) edge check |
BFS vs DFS decision guide:
| Signal | Choice |
|---|---|
| "Shortest path in unweighted graph" | BFS (queue) |
| "Does a path exist?" | Either |
| "Topological order" | BFS (Kahn's) or DFS |
| "Detect cycle" | DFS with recursion stack |
| "Connected components" | Either (DFS is simpler) |
| "All paths from A to B" | DFS (backtracking) |
| "Level order / layers" | BFS |
| "Maze shortest path" | BFS |
| "Maze find any exit" | DFS (simpler) |
When NOT to use a graph:
Forgetting the visited set (infinite loop) Without tracking visited nodes, BFS/DFS will revisit nodes and loop forever in a cyclic graph. Always initialize a visited set before traversal and check it before enqueuing/exploring.
Confusing directed and undirected graphs
In an undirected graph, add both directions: graph[u].Add(v) AND graph[v].Add(u). In a directed graph, only add one direction. Missing this causes wrong answers.
"BFS always finds the shortest path" Only for unweighted graphs. In weighted graphs, BFS does NOT find the shortest path - use Dijkstra's algorithm instead.
DFS recursion depth in large graphs A DFS on a graph with 100,000 nodes might recurse 100,000 levels deep. Stack overflow! Use explicit stack (iterative DFS) for large graphs.
Confusing BFS and DFS approaches BFS = queue (level by level). DFS = stack/recursion (depth first). Using the wrong one wastes time or gives wrong answers. For shortest path in an unweighted graph, always choose BFS.
Not handling disconnected components Most graph problems assume a connected graph. If the graph has multiple components, make sure your traversal covers ALL nodes by looping over all vertices and starting a new traversal for any unvisited node.