Graph Traversal: BFS & DFS

To traverse a graph is to visit every vertex reachable from a starting vertex. Unlike a tree, a graph can have cycles, so we keep a visited array to avoid looping forever.

#Breadth-first search (BFS)

BFS visits the start, then all its neighbours, then all their unvisited neighbours — expanding outward in rings, like ripples in water. It uses a queue.

1. Mark the start visited and enqueue it.
2. While the queue is not empty: dequeue a vertex, visit it, and enqueue each unvisited neighbour (marking it visited).

#Depth-first search (DFS)

DFS goes as deep as possible along one path before backtracking. It uses a stack — usually the call stack, via recursion.

1. Visit the vertex and mark it visited.
2. For each unvisited neighbour, recursively DFS from it.

#Step through both

Pick a start vertex and step through BFS or DFS. Watch the queue or stack and the visit order:

#BFS and DFS in C

#include <stdio.h>

#define V 7
int adj[V][V];
const char *name = "ABCDEFG";
int visited[V];

void addEdge(int u, int v) { adj[u][v] = adj[v][u] = 1; }

void bfs(int start) {
    int queue[V], front = 0, rear = 0, dist[V];
    for (int i = 0; i < V; i++) visited[i] = 0;
    visited[start] = 1; dist[start] = 0;
    queue[rear++] = start;
    printf("BFS: ");
    while (front < rear) {
        int u = queue[front++];
        printf("%c(%d) ", name[u], dist[u]);
        for (int v = 0; v < V; v++)
            if (adj[u][v] && !visited[v]) {
                visited[v] = 1;
                dist[v] = dist[u] + 1;      // one more edge than its parent
                queue[rear++] = v;
            }
    }
    printf("\n");
}

void dfs(int u) {
    visited[u] = 1;
    printf("%c ", name[u]);
    for (int v = 0; v < V; v++)
        if (adj[u][v] && !visited[v]) dfs(v);
}

int main(void) {
    // A-B, A-C, B-D, B-E, C-F, E-F, F-G
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 5}, {5, 6}};
    for (int i = 0; i < 7; i++) addEdge(e[i][0], e[i][1]);
    bfs(0);
    for (int i = 0; i < V; i++) visited[i] = 0;
    printf("DFS: ");
    dfs(0);
    printf("\n");
    return 0;
}

BFS: A(0) B(1) C(1) D(2) E(2) F(2) G(3) 
DFS: A B D E F C G

The number in brackets after each BFS vertex is its distance (in edges) from A — BFS finds shortest paths in unweighted graphs.

#BFS vs DFS

#Applications

• Connected components: run DFS/BFS from every unvisited vertex; each run discovers one component.
• Cycle detection: in DFS, reaching a visited vertex that is not your parent means a cycle (undirected graphs).
• Topological sort of a DAG: output vertices in reverse order of DFS completion — see Graph Algorithms.
• Bipartite check: BFS-colour vertices in two colours; a conflict means not bipartite.