Spreading outward versus falling down a rabbit hole

Why trees never needed a visited set

Unit II's tree traversals never worried about visiting a node twice, because a tree has no cycles — there is exactly one path from the root to anywhere, so recursion could never loop back on itself. A graph has no such guarantee. Follow edges carelessly and you can walk A to B to C and straight back to A, forever.

Both traversals below therefore share one non-negotiable rule: keep a visited set, check it before entering any vertex, and never enter one already in it. Every graph algorithm this unit covers depends on this rule.

BFS: everyone one step away, first

LinkedIn suggests your direct connections' connections before it suggests someone three connections removed — it explores outward in rings, one degree at a time. Breadth-first search does exactly this: enqueue the start vertex, then repeatedly dequeue a vertex, visit it, and enqueue every unvisited neighbor. This is Unit II Lesson 3's level-order traversal, generalized from a tree to any graph — the same queue, the same mechanics, marking visited on enqueue instead of only on dequeue to guard against a cycle enqueuing the same vertex twice.

void bfs(Graph *g, int start)
{
    bool visited[MAX_VERTICES] = { false };
    int queue[MAX_VERTICES], front = 0, rear = -1, count = 0;

    visited[start] = true;
    rear = 0; queue[0] = start; count = 1;

    while (count > 0) {
        int v = queue[front];
        front = (front + 1) % MAX_VERTICES; count--;
        printf("%d ", v);

        for each neighbor n of v:
            if (!visited[n]) {
                visited[n] = true;   /* mark on enqueue, not dequeue */
                rear = (rear + 1) % MAX_VERTICES;
                queue[rear] = n; count++;
            }
    }
}

DFS: commit to one path until it ends

You have fallen down a video-recommendation rabbit hole: one video leads to a related one, which leads to another, ten videos deep, before you finally back out and try a different branch from where you started. Depth-first search does this on purpose: visit a vertex, then immediately recurse into an unvisited neighbor, going as deep as possible before backtracking to try a sibling path.

The recursive call stack plays the same role Unit II's threaded-tree discussion warned you it would — each pending call remembers exactly where to resume, which is why an explicit stack works identically when recursion is not available.

void dfs(Graph *g, int v, bool visited[])
{
    visited[v] = true;
    printf("%d ", v);

    for each neighbor n of v:
        if (!visited[n])
            dfs(g, n, visited);   /* commit deeper before trying a sibling */
}