Practice › Graphs
DFS of a Graph
Easy · Graphs · Asked at Amazon, Microsoft, Google, Samsung
Print the depth-first search order starting from node 1. From each node, try its neighbours in increasing order and go as deep as possible before backtracking. Print only the nodes reachable from node 1.
Input
First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).
Output
The DFS order, space-separated.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ m ≤ 5 · 10^4
Recursive DFS with sorted adjacency lists. An iterative version must push neighbours in reverse order to visit the smallest first.
Example 1
Input
5 4 1 2 1 3 2 4 3 5
Output
1 2 4 3 5
Example 2
Input
4 3 1 4 1 2 4 3
Output
1 2 4 3
Hints
- Sort each adjacency list so the smallest neighbour is tried first.
- Recursive DFS: visit a node, then recurse into each unvisited neighbour in order.
Approach
Build sorted adjacency lists. dfs(u): mark u, output it, then for each neighbour in increasing order call dfs(v) if v is unvisited. This goes as deep as possible before backtracking. For very deep graphs, use an explicit stack (pushing neighbours in reverse order) or a larger stack size, as the Java solution does.
Complexity: O(n + m log m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> seen;
vector<int> order;
void dfs(int u) {
seen[u] = true;
order.push_back(u);
for (int v : adj[u])
if (!seen[v]) dfs(v);
}
int main() {
int n, m;
cin >> n >> m;
adj.assign(n + 1, {});
seen.assign(n + 1, false);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto &a : adj) sort(a.begin(), a.end());
dfs(1);
for (size_t i = 0; i < order.size(); i++) cout << order[i] << (i + 1 < order.size() ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = data[2 + 2 * i], data[3 + 2 * i]
adj[u].append(v)
adj[v].append(u)
for a in adj:
a.sort()
seen = [False] * (n + 1)
order, stack = [], [1]
# iterative DFS: push neighbours in reverse so the smallest is explored first
while stack:
u = stack.pop()
if seen[u]:
continue
seen[u] = True
order.append(u)
for v in reversed(adj[u]):
if not seen[v]:
stack.append(v)
print(*order)Java solution
import java.util.*;
import java.io.*;
public class Main {
static List<List<Integer>> adj = new ArrayList<>();
static boolean[] seen;
static StringBuilder sb = new StringBuilder();
static void dfs(int u) {
seen[u] = true;
sb.append(sb.length() > 0 ? " " : "").append(u);
for (int v : adj.get(u))
if (!seen[v]) dfs(v);
}
public static void main(String[] args) throws Exception {
Thread t = new Thread(null, () -> {
try {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
in.nextToken();
int u = (int) in.nval;
in.nextToken();
int v = (int) in.nval;
adj.get(u).add(v);
adj.get(v).add(u);
}
for (List<Integer> a : adj) Collections.sort(a);
seen = new boolean[n + 1];
dfs(1);
System.out.println(sb);
} catch (IOException e) {
throw new RuntimeException(e);
}
}, "main", 1 << 26);
t.start();
t.join();
}
}