DFS: visitation, returns and traversal forests

Start with reachability

Depth-first search (DFS) explores one unvisited neighbor recursively before returning to consider the next neighbor. You will trace discovery and finish orders, explain visited markers, and distinguish a source traversal from a traversal of every vertex. Read “Graph terms and adjacency representations” and recall recursion: each call retains its own local variables and resumes its pending work after a child call returns. Arrays, loops, conditions and functions are prerequisites.

Our graph has n vertices numbered 0 through n−1, where 0 <= n <= 6. It is simple and undirected: no self-loops, no parallel edges, and an edge can be followed in either direction. The initialized 0/1 adjacency matrix is symmetric with a zero diagonal. An entry adj[u][v]=1 means an edge exists; 0 means it does not. The number is an existence flag, not a weight. All neighbor scans use increasing vertex numbers. A different source or neighbor order may give a different valid DFS order.

Discover, descend, return, finish

To enter an unseen vertex u:

1. Mark u seen immediately and append u to discovery order.
2. Scan v=0,1,...,n−1. For each adjacent, unseen v, make u its DFS parent, set its DFS depth to depth[u]+1, and recursively explore v completely.
3. After the entire neighbor scan, append u to finish order and return.

Discovery records first entry. Finish records the completion of all recursive work started by that call. Finish is not a second discovery: each reachable vertex appears once in each list. In this lesson “DFS traversal order” means discovery order unless finish order is explicitly requested. Finish order is not generally the reverse of discovery order, because a branching traversal can finish an early child before discovering a later child.

The caller pauses inside its loop while a child is explored. Its local u and v are retained. Once that child returns, the caller continues its own neighbor scan. A vertex with no unseen neighbor finishes immediately; a vertex need not have degree zero to do so.

Marking before recursion prevents repeated entry. On undirected edge 0–1, the call for 1 sees the edge back to 0 but skips 0 because it is already seen. In a cycle, an edge to any already-seen vertex is similarly skipped. A seen marker alone does not say whether that vertex is still active or already finished, and this program does not claim to classify edges or detect cycles. Encountering the parent edge in an undirected graph is normal.

Worked trace 1: a triangle is enough to disprove shortest depth

Use a new graph with vertices 0,1,2 and edges {0–1,0–2,1–2}. Start at 0, taking neighbors in increasing order.

The selected DFS tree edges are 0–1 and 1–2; graph edge 0–2 is still present but is not selected as a parent edge. Parents are NONE,0,1, and DFS depths are 0,1,2. However, vertex 2 is only ONE edge from 0 in the original graph. DFS depth counts parent edges in its chosen traversal tree; it does not guarantee the minimum number of edges from the source. This lesson teaches traversal, not shortest-path computation.

Worked trace 2: a branching return is not a reversed list

Return to the prerequisite graph: n=5 and edges {0–1,0–3,1–2,1–3,3–4}. From 0, discovery order is 0,1,2,3,4. Enter 0, then 1, then 2. Vertex 2 has only seen neighbor 1, so it finishes. The still-active call for 1 then explores 3, which explores 4. Finish events are 2,4,3,1,0.

The finish list is not the reversed discovery list 4,3,2,1,0. The important distinction is that 2 finishes before 3 is even discovered. Parents are NONE,0,1,1,3 and depths are 0,1,2,2,3. Every nonroot parent was discovered earlier, and each child finishes before its parent. These facts do not require all siblings to finish in reverse discovery order.

Worked trace 3: one source versus a full forest

The program below uses six vertices: triangle {0,1,2}, one edge 3–4, and isolated vertex 5. There are three connected components. A fresh source traversal from 0 discovers only 0,1,2 and finishes 2,1,0. Vertices 3,4,5 remain unseen; their parent and depth remain NONE. That is a complete answer to reachability from 0, not a failure.

For a full traversal, keep ONE shared marker array and scan candidate roots 0,1,...,5. At 0, start DFS and exhaust its component. Skip already-seen 1 and 2. Start at unseen 3, which discovers 4; skip 4 afterward. Finally start at isolated 5. Discovery is 0,1,2,3,4,5; finish is 2,1,0,4,3,5. Root count is 3. Each new root has parent NONE and depth 0; depths are measured within each tree, not all from vertex 0. Never clear seen between candidate roots: doing so would revisit components.

In this undirected graph, the number of DFS forest roots equals the number of connected components, including isolated vertices. A directed traversal instead follows outgoing arcs. Its reachable set and its outer-loop DFS forest must not automatically be called undirected, weakly connected or strongly connected components. For example, with only directed arc 1→0, an increasing-root outer loop starts at both 0 and 1 even though ignoring direction gives one connected component. Our validator deliberately accepts only undirected inputs.

Bounded records and storage contract

Graph is a record holding n and the 6×6 matrix. Traversal is a record holding shared markers, parent/depth arrays, two order arrays, their lengths, and the root count. All storage is fixed size; there is no dynamic allocation. Only indices less than n are graph vertices. Unused matrix cells are ignored by validation and traversal. Only the first discovered or finished entries of the corresponding order array are meaningful; a zero in an unused slot is not an extra visit to vertex 0.

The caller must supply live, initialized Graph and Traversal objects at distinct, non-overlapping addresses. Both pointers must be non-null and valid; the validator cannot test object lifetimes or actual storage. The graph stays unchanged during traversal, and calls are sequential. valid_graph checks 0<=n<=CAP, active entries being 0/1, a zero diagonal, and symmetry before traversal. Self-loops and asymmetric matrices are invalid under this representation contract. Cycles such as the triangle are valid.

Both public traversal functions reset the result on each call. They return 1 on success and 0 on an invalid graph or, for dfs_source, invalid source. An empty graph n=0 is valid: dfs_forest succeeds with empty orders and zero roots, but dfs_source has no valid source and fails. The internal visit helper is not a stand-alone validator; call it only through these wrappers, which ensure its vertex is valid and unseen and its root depth is initialized.

Complete C11 program

Predict the output before running. The output reports vertices, not matrix entries.

#include <stdio.h>

enum { CAP = 6, NONE = -1 };

typedef struct {
    int n;
    int adj[CAP][CAP];
} Graph;

typedef struct {
    int seen[CAP];
    int parent[CAP];
    int depth[CAP];
    int discovery[CAP];
    int finish[CAP];
    int discovered;
    int finished;
    int roots;
} Traversal;

int valid_graph(const Graph *g) {
    if (g->n < 0 || g->n > CAP) {
        return 0;
    }
    for (int u = 0; u < g->n; ++u) {
        for (int v = 0; v < g->n; ++v) {
            if ((g->adj[u][v] != 0 && g->adj[u][v] != 1) ||
                (u == v && g->adj[u][v] != 0) ||
                g->adj[u][v] != g->adj[v][u]) {
                return 0;
            }
        }
    }
    return 1;
}

void reset_traversal(Traversal *t) {
    *t = (Traversal){0};
    for (int v = 0; v < CAP; ++v) {
        t->parent[v] = NONE;
        t->depth[v] = NONE;
    }
}

/* Internal helper: validated graph; u is valid and not yet seen. */
void visit(const Graph *g, int u, Traversal *t) {
    t->seen[u] = 1;
    t->discovery[t->discovered] = u;
    ++t->discovered;
    for (int v = 0; v < g->n; ++v) {
        if (g->adj[u][v] == 1 && !t->seen[v]) {
            t->parent[v] = u;
            t->depth[v] = t->depth[u] + 1;
            visit(g, v, t);
        }
    }
    t->finish[t->finished] = u;
    ++t->finished;
}

int dfs_source(const Graph *g, int source, Traversal *t) {
    reset_traversal(t);
    if (!valid_graph(g) || source < 0 || source >= g->n) {
        return 0;
    }
    t->roots = 1;
    t->depth[source] = 0;
    visit(g, source, t);
    return 1;
}

int dfs_forest(const Graph *g, Traversal *t) {
    reset_traversal(t);
    if (!valid_graph(g)) {
        return 0;
    }
    for (int v = 0; v < g->n; ++v) {
        if (!t->seen[v]) {
            ++t->roots;
            t->depth[v] = 0;
            visit(g, v, t);
        }
    }
    return 1;
}

void print_order(const char *label, const int order[], int count) {
    printf("%s", label);
    for (int i = 0; i < count; ++i) {
        printf(" %d", order[i]);
    }
    printf("\n");
}

#ifndef DFS_NO_MAIN
int main(void) {
    Graph g = {6, {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 1, 0, 0, 0},
        {1, 1, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0}
    }};
    Traversal t = {0};
    if (!dfs_source(&g, 0, &t)) {
        return 1;
    }
    print_order("source discovery:", t.discovery, t.discovered);
    print_order("source finish:", t.finish, t.finished);
    printf("source depth of 2: %d\n", t.depth[2]);
    if (!dfs_forest(&g, &t)) {
        return 1;
    }
    print_order("forest discovery:", t.discovery, t.discovered);
    print_order("forest finish:", t.finish, t.finished);
    printf("forest roots: %d\n", t.roots);
    return 0;
}
#endif

Exact output:

source discovery: 0 1 2
source finish: 2 1 0
source depth of 2: 2
forest discovery: 0 1 2 3 4 5
forest finish: 2 1 0 4 3 5
forest roots: 3

Read the new syntax and safety argument

“typedef struct” gives a record type a short name. Graph g={6,{...}} initializes n and the nested matrix rows. Traversal t={0} zero-initializes every field. reset_traversal assigns a fresh all-zero record with the C11 compound literal (Traversal){0}, then sets every parent and depth to NONE=-1. This sentinel denotes no parent or no discovered depth; it is never used as an array index.

&g and &t take addresses. Graph * and Traversal * parameters point to the caller's actual records; g->n selects a field through a pointer, equivalent to (*g).n. const Graph * permits reading but not modifying the graph through that pointer. The mutable Traversal * makes recursive calls share the same markers and output arrays. Each call still has its own local loop variables. The arrays are not copied on recursive entry. Array parameters in print_order similarly refer to existing storage. Its const char *label parameter points to a null-terminated text string, and %s prints that string; the string literal labels supplied by main provide valid storage and the terminating zero character.

The || operator short-circuits; source range is checked before visit is called. && evaluates its right operand only if the left is true. !t->seen[v] means v has not been marked; ++ increments by one. The braces in the reset expression make a temporary initialized record value, rather than allocating new storage dynamically. <stdio.h> declares printf; %d prints an int; \n ends a line. #ifndef DFS_NO_MAIN lets the separate test file include the helpers without a second main; ordinary compilation includes the demonstration main.

Each recursive entry marks a previously unseen vertex, so there are at most n entries in one traversal and at most n simultaneously active visit calls. An isolated root still has one call and appears in both orders. The largest depth is at most n−1 (at most 5 here). Output lengths never exceed n, so the fixed arrays are sufficient. This bounded demonstration does not promise safe call-stack space for arbitrarily large graphs.

With an n×n matrix, validation is O(n²). Visiting r reachable vertices scans n columns per vertex: O(rn), plus initialization; the full forest is O(n²). Including the supplied validator makes even source traversal O(n²) overall. The usual O(n+m) DFS bound assumes an adjacency-list representation, not scanning every matrix row. Matrix storage is O(n²); markers, parent/depth, orders and recursive stack need O(n) extra space in the generalized version. Here CAP=6 fixes all concrete storage bounds.

A bounded analogy

Imagine up to six labeled rooms joined by two-way doors, with no door from a room back into itself and no duplicate door pair. Keep one notebook of already-entered rooms. On entering a new room, mark it before taking the lowest-numbered unvisited neighboring room. Finish a room's checklist only after returning from every exploration started there. The notebook models shared seen markers and returning models recursive pending work. It is not a shortest-route planner: choosing a door first can create a long exploration route even when a direct door exists. Separate buildings model disconnected components and an isolated room still needs its own start.

Key box

• Mark before descent; recurse only into unseen adjacent vertices.
• Discovery is first entry; finish is after all child calls and the full neighbor scan.
• A source call finds exactly the vertices reachable from that source.
• An ascending outer loop with shared markers gives a full DFS forest.
• For this undirected model, forest roots count connected components.
• DFS parent depth need not equal shortest-path distance.
• Matrix DFS scans n columns per visited vertex; list-based complexity is different.
• Validate the bounded representation and source before internal recursion.

Two extra exercises

1. In the six-vertex program, use source 4. Predict both orders and all discovered depths. Answer: discovery 4,3; finish 3,4; depth[4]=0 and depth[3]=1. Others remain NONE and unseen. Starting in a different component does not cause an automatic jump to vertex 0.
2. Use n=3 with no edges. Compare source 1 with a full forest. Answer: source discovery and finish are both [1], with one root. Full discovery and finish are both [0,1,2], with three roots, each depth 0. Equal lists here do not imply the two event definitions are identical.

This is an introductory traversal lesson with original exercises. Shortest-path algorithms, topological sorting and cycle/edge classification need separate lessons; these exercises are not past exam questions or complete syllabus coverage.

Six original practice questions

Choose exactly one option.

1

In the triangle {0–1,0–2,1–2}, source 0 scans neighbors in ascending order. What are discovery and finish orders?

A. Discovery 0,1,2; finish 2,1,0 B. Discovery 0,2,1; finish 1,2,0 C. Discovery 0,1,2; finish 0,1,2 D. Discovery 0,1,0,2; finish 2,0,1,0

2

For n=4 with edges {0–1,2–3}, a fresh source DFS starts at 1. Which vertices are discovered?

A. All four vertices automatically B. Only 1 C. Exactly 1 and 0 D. Exactly 1,0,2

3

Why must the shared seen marker be set before recursive neighbor calls?

A. It sorts all graph vertices B. It makes DFS depth a shortest distance C. It removes every graph cycle D. It prevents a back edge from re-entering the same still-active vertex

4

From source 0, the graph {0–1,0–2,1–2} gives parent[2]=1 and depth[2]=2. Which interpretation is valid?

A. Every path from 0 to 2 has two edges B. The selected DFS parent path has two edges, although an original one-edge path exists C. The graph has no edge 0–2 D. Vertex 2 was discovered twice

5

For an empty valid graph n=0, what do the provided wrappers do?

A. Both reject the graph as malformed B. dfs_source with source 0 succeeds and discovers 0 C. dfs_forest succeeds with zero roots; dfs_source with source 0 fails D. dfs_forest creates one empty root

6

For n=5, edges {0–1,0–3,1–2,1–3,3–4}, source 0 and ascending neighbors, which is the finish order?

A. 2,4,3,1,0 B. 4,3,2,1,0 C. 0,1,2,3,4 D. 2,1,4,3,0

Worked answers

1: A

A is correct: 0 descends to 1 then 2; the calls finish from deepest to root.

B is incorrect: choosing 2 before 1 violates the stated ascending neighbor order.

C is incorrect: 0 cannot finish before its unfinished child calls.

D is incorrect: 0 was marked before descent and cannot be discovered again.

2: C

A is incorrect: a source call has no outer loop to start disconnected components.

B is incorrect: unseen neighbor 0 is reachable from 1.

C is correct: edge 1–0 joins the two reachable vertices; neither 2 nor 3 is reachable.

D is incorrect: there is no path from 1 to 2; traversal does not jump by vertex number.

3: D

A is incorrect: marking records visitation, not numerical sorting.

B is incorrect: the triangle still gives DFS depth 2 for a vertex one edge from the source.

C is incorrect: traversal does not modify the graph or remove edges.

D is correct: an adjacent call sees the marker and skips re-entry, even before the earlier call finishes.

4: B

A is incorrect: the direct edge 0–2 is a one-edge path.

B is correct: depth measures the selected tree path 0–1–2, not a shortest-path guarantee.

C is incorrect: an edge can exist without being chosen as a DFS parent edge.

D is incorrect: depth counts parent edges, not discovery multiplicity.

5: C

A is incorrect: zero vertices is allowed by the graph contract.

B is incorrect: with n=0 there is no valid vertex index 0.

C is correct: the forest loop has no iterations, and the source range check rejects 0.

D is incorrect: roots are actual discovered vertices; the empty graph contains none.

6: A

A is correct: 2 finishes first; then 1 explores 3 and 4, which finish before 1 and 0.

B is incorrect: reversing discovery incorrectly places 2 after 3 and 4, which are discovered only after 2 finishes.

C is incorrect: this is discovery order; the root finishes last.

D is incorrect: 1 cannot finish before exploring its still-unseen neighbor 3 and the descendant 4.