Depth first traversal in graph

Depth first traversal (DFS) visits the vertices of a graph by going as deep as possible along a path before backtracking. It starts from a source vertex, marks it visited, then moves to an unvisited neighbour, and continues until a vertex has no unvisited neighbour; then it backtracks to the previous vertex and tries the next neighbour. It uses a stack (or recursion).

Algorithm (using a stack)

DFS(G, start)
1. push start on stack, mark start visited, print it
2. while stack not empty
3.     v = top of stack
4.     if v has an unvisited neighbour w
5.         mark w visited, print w, push w
6.     else  pop stack          // backtrack

Recursive version:

int adj[N][N], visited[N], n;
void dfs(int v) {
    visited[v] = 1;
    printf("%d ", v);
    for (int w = 0; w < n; w++)
        if (adj[v][w] && !visited[w])
            dfs(w);
}

Example

        A
       / \
      B   C
     / \   \
    D   E---F

Edges: A-B, A-C, B-D, B-E, C-F, E-F. Adjacency lists (alphabetical): A: B, C; B: A, D, E; C: A, F; D: B; E: B, F; F: C, E.

Start at A, choosing neighbours in alphabetical order:

DFS order: A B D E F C

Complexity: O(V + E) with adjacency lists, O(V²) with an adjacency matrix. Uses: cycle detection, topological sort, connected components, path finding.