A graph models entities as vertices and relationships as edges. Choose an adjacency list for most sparse graphs and an adjacency matrix when constant-time edge lookup justifies the extra space.
Use BFS for level-order exploration and shortest paths in unweighted graphs; use DFS for deep traversal, components, and cycle-oriented reasoning. Mark a vertex when it is scheduled so cycles do not create duplicate work.
An adjacency list stores only existing edges and is efficient for sparse graphs. An adjacency matrix uses a grid and is useful when edge lookup must be constant-time or the graph is dense.
BFS explores level by level and is useful for shortest path in an unweighted graph. DFS explores deeply first and is useful for connected components, cycle detection, and topological-style reasoning.
Many advanced problems are graph problems with different names: dependency ordering, islands in a grid, friend circles, route planning, deadlock detection, and package installation order.
Starting BFS or DFS from one vertex visits only its reachable component. To traverse a general graph, iterate over every vertex and launch a traversal whenever that vertex is still unvisited. This outer loop changes the contract from component traversal to complete graph traversal.
Mark visited state when work is scheduled, not after it is processed. In BFS, marking on enqueue prevents several parents from adding the same vertex. In iterative DFS, the same rule prevents unnecessary stack growth. Decide whether visited state belongs to one operation or persists across operations; stale shared state can make later traversals skip valid vertices.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> graph = {
{1, 2},
{0, 3},
{0},
{1}
};
vector<bool> visited(graph.size(), false);
queue<int> q;
q.push(0);
visited[0] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << ' ';
for (int next : graph[node]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
}#include <iostream>
#include <vector>
using namespace std;
void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
visited[node] = true;
cout << node << ' ';
for (int next : graph[node]) {
if (!visited[next]) {
dfs(next, graph, visited);
}
}
}#include <vector>
using namespace std;
void dfs(int node, vector<vector<int>>& graph, vector<bool>& seen) {
seen[node] = true;
for (int next : graph[node]) {
if (!seen[next]) dfs(next, graph, seen);
}
}
int components(vector<vector<int>>& graph) {
vector<bool> seen(graph.size(), false);
int count = 0;
for (int i = 0; i < (int)graph.size(); i++) {
if (!seen[i]) {
count++;
dfs(i, graph, seen);
}
}
return count;
}
#include <vector>
#include <utility>
using namespace std;
int main() {
vector<vector<pair<int, int>>> graph(3);
graph[0].push_back({1, 7});
graph[0].push_back({2, 4});
graph[1].push_back({2, 2});
}
BFS explores level by level with a queue; DFS follows one path at a time with recursion or a stack.
Use a list for sparse graphs because it stores only existing edges.
Without a visited set, cycles can cause repeated work or an infinite traversal.
Explore 500+ free tutorials across 20+ languages and frameworks.