Depth-First Search (Recursive)

Visit a start vertex, then recurse into its first unvisited neighbour all the way down before backtracking. A visited array prevents revisiting, and neighbour insertion order fixes the visit sequence.

Algorithm

Basic Implementation

basic.c

#include <stdio.h>
#include <stdbool.h>

#define V 7
#define MAX_DEG 4

int adj[V][MAX_DEG] = {
    {-1, -1, -1, -1},
    { 2,  3, -1, -1},
    { 1,  4, -1, -1},
    { 1,  4, -1, -1},
    { 2,  3,  5, -1},
    { 4,  6, -1, -1},
    { 5, -1, -1, -1},
};
bool visited[V];
int order[V];
int order_n = 0;

void dfs(int v) {
    visited[v] = true;
    order[order_n++] = v;
    for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
        int nb = adj[v][k];
        if (!visited[nb]) {
            dfs(nb);
        }
    }
}

int main(void) {
    dfs(1);
    printf("[");
    for (int i = 0; i < order_n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", order[i]);
    }
    printf("]\n");
    return 0;
}

DFS follows the first unvisited neighbour as far as it can, then unwinds and tries the next branch.

Step 1 - First branch

Starting from 1, insertion order sends DFS to 2, then 4, then 3.

Step 2 - Full DFS order

The final order is [1, 2, 4, 3, 5, 6], then calls unwind 6 -> 5 -> 4 -> 3 -> 2 -> 1.

Complexity

Time: O(V + E)
Space: O(V) recursion depth

Implementation notes

C: file-scope adj, visited, and order arrays let the recursive dfs(int v) share state; recursion depth is bounded by V.
The replay shows the current vertex, the visited set, the running visit order, and the call stack after each entry, matching the lesson spec.

recursive descent Follow one branch to its end, then unwind and try the next neighbour.