DFS and BFS Explanation and Traversal
in C
The question asks for an explanation of the DFS (Depth First Search) and BFS (Breadth First
Search) algorithms and their traversal on the given graph.
1. DFS (Depth First Search)
DFS explores as far as possible along each branch before backtracking. It uses a stack (or
recursion) for its implementation.
Steps:
1. Start at a chosen node (say node 0).
2. Visit the node, mark it as visited.
3. Move to an adjacent, unvisited node and repeat.
4. If no unvisited adjacent node is found, backtrack to the last visited node and continue
from there.
DFS Traversal Example (starting at node 0):
Start at node 0.
Move to node 1.
Move to node 3.
Backtrack to node 1, and then visit node 4.
Move to node 7, then to node 6.
Backtrack to node 7, visit node 5, then backtrack to complete the traversal.
DFS Traversal: 0 -> 1 -> 3 -> 4 -> 7 -> 6 -> 5 -> 2
2. BFS (Breadth First Search)
BFS explores all neighbors of a node before moving on to the next level of nodes. It uses a
queue for its implementation.
Steps:
1. Start at the chosen node (say node 0).
2. Visit the node, mark it as visited.
3. Add all adjacent unvisited nodes to a queue.
4. Visit the next node in the queue and repeat until all nodes are visited.
BFS Traversal Example (starting at node 0):
Start at node 0.
Visit nodes 1, 2 (neighbors of 0).
Visit nodes 3, 4 (neighbors of 1 and 2).
Visit nodes 7 (neighbor of 4), then nodes 6 and 5 (neighbors of 7).
BFS Traversal: 0 -> 1 -> 2 -> 3 -> 4 -> 7 -> 6 -> 5
3. DFS and BFS Implementation in C
DFS Algorithm (using recursion):
#include <stdio.h>
int graph[8][8] = { // Adjacency matrix for the given graph
{0, 1, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 1, 1, 0}
};
int visited[8] = {0};
void DFS(int node) {
printf("%d ", node);
visited[node] = 1;
for (int i = 0; i < 8; i++) {
if (graph[node][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
int main() {
printf("DFS Traversal: ");
DFS(0); // Start DFS at node 0
return 0;
}
BFS Algorithm (using queue):
#include <stdio.h>
int graph[8][8] = { // Same adjacency matrix
{0, 1, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 1, 1, 0}
};
int visited[8] = {0};
void BFS(int start) {
int queue[8], front = 0, rear = 0;
printf("%d ", start);
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int node = queue[front++];
for (int i = 0; i < 8; i++) {
if (graph[node][i] == 1 && !visited[i]) {
printf("%d ", i);
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
int main() {
printf("BFS Traversal: ");
BFS(0); // Start BFS at node 0
return 0;
}
