SimuVedaAlgorithms Lab Open in the lab

Graphs / Beginner

Depth-First Search Visualizer

Go as deep as possible along one path, then back up and try the next branch. The call stack remembers where to return.

Start the Depth-First Search simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(V+E)
Average timeO(V+E)
Worst timeO(V+E)
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Call dfs(A) and mark A seen.
  2. Visit A.
  3. B is not seen yet. Go deeper into B.
  4. Call dfs(B) and mark B seen.
  5. Visit B.
  6. A was already seen. Skip it.
  7. C is not seen yet. Go deeper into C.
  8. Call dfs(C) and mark C seen.
  9. Visit C.
  10. A was already seen. Skip it.
  11. B was already seen. Skip it.
  12. D is not seen yet. Go deeper into D.
  13. Call dfs(D) and mark D seen.
  14. Visit D.
  15. B was already seen. Skip it.
  16. C was already seen. Skip it.
  17. E is not seen yet. Go deeper into E.
  18. Call dfs(E) and mark E seen.
  19. Visit E.
  20. C was already seen. Skip it.
  21. … 13 more steps …
  22. B has no unseen neighbors left. Return to A.
  23. C was already seen. Skip it.
  24. A has no unseen neighbors left. Return.
  25. Done. Visit order: A, B, C, D, E, F.

Try it with your own input →

Depth-first search in Java, Python, C++, C and JavaScript

void dfs(int u, boolean[] seen) {
  seen[u] = true;
  visit(u);
  for (int v : adj[u]) {
    if (!seen[v]) {
      dfs(v, seen);
    }
  }
}
def dfs(adj, u, seen):
    seen[u] = True
    visit(u)
    for v in adj[u]:
        if not seen[v]:
            dfs(adj, v, seen)
void dfs(const vector<vector<int>>& adj, int u, vector<bool>& seen) {
  seen[u] = true;
  visit(u);
  for (int v : adj[u]) {
    if (!seen[v]) {
      dfs(adj, v, seen);
    }
  }
}
#define MAXN 100
int adj[MAXN][MAXN], deg[MAXN];

void dfs(int u, int seen[]) {
  seen[u] = 1;
  visit(u);
  for (int k = 0; k < deg[u]; k++) {
    int v = adj[u][k];
    if (!seen[v]) {
      dfs(v, seen);
    }
  }
}
function dfs(adj, u, seen) {
  seen[u] = true;
  visit(u);
  for (const v of adj[u]) {
    if (!seen[v]) {
      dfs(adj, v, seen);
    }
  }
}

In an interview

DFS is the base for cycle detection, topological sort, connected components and most backtracking problems.

More graphs