Graph Traversal: DFS and BFS

Tree traversal visits every node exactly once, since a tree has no cycles and each non-root node has only one parent, so no node is ever reached twice. A graph has neither guarantee, since a vertex can have multiple incoming edges and a cycle can lead back to one already visited, so graph traversal needs an explicit visited marker to avoid looping forever.

Depth First Search (DFS)

DFS(V)
// V is the vertex to visit next
 
1. visited[V] = TRUE
2. PRINT V
3. For each adjacent vertex U of V:
       If visited[U] == FALSE:
           DFS(U)

Before starting, every vertex is marked unvisited: visited[v] = false for all v. The adjacent vertices of V come from whichever representation the graph is stored in: for an adjacency matrix, scan V's row and collect every column with a 1; for an adjacency list, V's list already is that set of neighbors. If a question specifies an order for picking among multiple choices (e.g. ascending), that order is followed at each step.

DFS from A, choosing neighbors alphabetically:

(DFS(A), Steps 1-2) Mark A visited and visit it. (Step 3) Its neighbors are B, C (alphabetical order), both unvisited, so the first recursive call is DFS(B):

(DFS(B), Steps 1-2) Mark B visited and visit it. (Step 3) Its only neighbor is D (A is already visited, so it is skipped), so the next recursive call is DFS(D):

(DFS(D), Steps 1-2) Mark D visited and visit it. (Step 3) D has no unvisited neighbors, so DFS(D) returns, DFS(B) returns (its loop over neighbors is done), and control returns to DFS(A)'s loop, which still has C left to try:

(DFS(C), Steps 1-2) Mark C visited and visit it. (Step 3) C has no unvisited neighbors, so DFS(C) returns, and since A's loop has no vertices left, DFS(A) also returns: the traversal is done.

DFS order: A B D C. DFS went as deep as possible through B → D before ever backtracking to visit C, which is the defining "depth first" behavior.

DFS visits every vertex and every edge at most once, so its time complexity depends only on how quickly the adjacent vertices of each V can be found:

Breadth First Search (BFS)

BFS(S)
// S is the source vertex to start from
 
1. For every vertex V:
       visited[V] = FALSE
2. visited[S] = TRUE
3. Q = empty queue
4. ENQUEUE(Q, S)
5. While Q is not empty:
       V = DEQUEUE(Q)
       PRINT V
       For each adjacent vertex U of V:
           If visited[U] == FALSE:
               visited[U] = TRUE
               ENQUEUE(Q, U)

BFS from A, same graph, using the same visual convention: highlighted nodes are visited, and the queue is shown after each step.

(BFS(A), Steps 1-4) All vertices start unvisited, then A is marked visited and enqueued: visited = {A}, Queue = [A].

(Step 5, first pass) Dequeue A and visit it. Its neighbors B, C are both unvisited, so both are marked visited and enqueued: Queue = [B, C].

(Step 5, second pass) Dequeue B and visit it. Its neighbor D is unvisited, so it is marked visited and enqueued: Queue = [C, D].

(Step 5, third pass) Dequeue C and visit it. It has no unvisited neighbors, so nothing is enqueued: Queue = [D].

(Step 5, fourth pass) Dequeue D and visit it. It has no unvisited neighbors: Queue = []. The queue is now empty, so the While loop ends.

BFS order: A B C D. Both of A's direct neighbors (B, C) are visited before D, which is two steps away. This level-by-level pattern is what DFS does not have.

Like DFS, BFS visits every vertex and every edge at most once, so its time complexity depends on the same factor, how quickly the adjacent vertices of each dequeued V can be found:

DFS vs BFS

DFS stands for Depth First Search: it explores one branch as deep as possible before backtracking. BFS stands for Breadth First Search: it explores every neighbor at the current depth (breadth) before moving deeper.

KTU PYQ: BFS

BFS(S)
// S is the source vertex to start from
 
1. For every vertex V:
       visited[V] = FALSE
2. visited[S] = TRUE
3. Q = empty queue
4. ENQUEUE(Q, S)
5. While Q is not empty:
       V = DEQUEUE(Q)
       PRINT V
       For each adjacent vertex U of V:
           If visited[U] == FALSE:
               visited[U] = TRUE
               ENQUEUE(Q, U)

Shortest Path: Single Source, All Destination

For an unweighted graph, BFS is the standard method: since BFS visits vertices in order of how many edges away they are from the source, the first time a vertex is dequeued, that's its shortest distance (in edge count) from the source.

For a weighted graph with non-negative weights, the standard method is Dijkstra's algorithm. Before looking at the full algorithm, it helps to understand its core repeated step, called relaxation.

What relaxation means

Dijkstra maintains a tentative distance[v] for every vertex: 0 for the source and ∞ for all others. Whenever a vertex is finalized, Dijkstra tries to improve the distances of its neighbors by relaxing the edges leading to them.

The diagram below shows one such moment: A has already been finalized with distance[A] = 5 (the accent-colored number under each vertex is its current distance[v]), and B has not been reached yet.

Before relaxation: distance[A] = 5 (finalized) and distance[B] = ∞ (not yet reached).

Relaxing the edge A → B means checking whether going through A gives B a shorter distance than what it currently has:

distance[B] = min(distance[B], distance[A] + weight(A,B))
            = min(∞, 5 + 3)
            = 8

After relaxation: distance[B] becomes 8. Updating a vertex's distance whenever a shorter path is found is what relaxation means.

Dijkstra's algorithm

DIJKSTRA(G, SOURCE)
// distance[v] is the shortest known distance from SOURCE to v
// visited[v] indicates whether v has been finalized
// |V| is the number of vertices in G
 
1. For each vertex v in G:            // start every vertex unreached
       distance[v] = INFINITY
       visited[v] = FALSE
 
2. distance[SOURCE] = 0                // the source is 0 away from itself
 
3. For i = 1 to |V|:                   // finalize one vertex per iteration
 
       u = -1
       minDistance = INFINITY
 
       For each vertex v in G:         // find the closest unvisited vertex
           If visited[v] = FALSE AND distance[v] < minDistance:
               minDistance = distance[v]
               u = v
 
       visited[u] = TRUE               // finalize u
 
       For each neighbor v of u:       // relax every edge out of u
           newDistance = distance[u] + weight(u, v)
 
           If newDistance < distance[v]:
               distance[v] = newDistance
 
4. Return distance[]

Worked example: the table method

Graph, source A. Every edge weight is labeled on its line:

The table method shows the distance table one row at a time, with a new row added after each vertex is finalized, so the process of filling it in is visible, not just the finished table. ∞ means "not yet reached." Once a column's value is bold, that vertex is finalized, and its value is locked in and will never change in a later row.

Initialize. distance[A] = 0 (the source), every other vertex ∞:

Step 1: finalize A (distance 0, the source). Relax A's neighbors: distance[B] = min(∞, 0+4) = 4, distance[C] = min(∞, 0+2) = 2. Add a new row with just these two cells changed:

Step 2: finalize C (smallest unfinalized distance in the row above, 2). Relax C's neighbors: distance[D] = min(∞, 2+8) = 10, distance[E] = min(∞, 2+10) = 12. A and B carry forward unchanged, C becomes bold (finalized):

Step 3: finalize B (smallest unfinalized distance, 4, beating D's 10 and E's 12). Relax B's neighbors: distance[D] = min(10, 4+5) = 9 (improved), distance[E] = min(12, 4+6) = 10 (improved). Both D and E change this row, even though neither is finalized yet:

Step 4: finalize D (smallest unfinalized distance, 9). Relax D's only unfinalized neighbor, E: distance[E] = min(10, 9+2) = min(10, 11) = 10, no improvement (11 > 10), so E's value carries forward unchanged from step 3:

Step 5: finalize E (only vertex left, distance 10). No unfinalized neighbors remain to relax. Every column is now bold, done:

Final shortest distances from A: A=0, B=4, C=2, D=9, E=10. The shortest path to D, for instance, is A → B → D (cost 4+5=9), not the direct A → C → D (cost 2+8=10), even though C was finalized before B. Dijkstra does not commit to a full path early, only to individual vertex distances, one at a time.

Complexity

Quick recall

• Graph traversal needs an explicit visited marker, since graphs (unlike trees) can contain cycles.
• DFS: stack/recursion, explores deep before backtracking, O(V+E) with an adjacency list.
• BFS: queue, explores level by level, mark visited at enqueue time to avoid duplicate enqueues, O(V+E) with an adjacency list.
• BFS gives shortest paths by edge count in unweighted graphs, and is the algorithm this module's DFS/BFS coverage directly supports for the "single source all destination" application.
• Dijkstra: greedy, repeatedly finalizes the closest unvisited vertex and relaxes its neighbors; requires non-negative weights. O(V²) with an array scan, O((V+E) log V) with a priority queue.
• Dijkstra's table method: one row per finalized vertex, tracking distance[v] for every vertex, values only ever decrease and freeze once a vertex is finalized.
• "Single source, all destination": one source, distances/paths to every reachable vertex.

That covers every topic in Module 3. For a focused list of the questions most likely to appear from this module, see Most Expected Questions.