Graph Traversal
Published by: Anil K. Panta
Graph Traversal | DFS and BFS
Traversing a graph means visiting all its vertices. This is essential in algorithms such as path finding, cycle detection, topological sorting, and more.
Two major techniques to traverse a graph are:
- Depth First Search (DFS)
- Breadth First Search (BFS)
What is DFS (Depth First Search)?
DFS explores a graph by moving as far from the starting node as possible before backtracking.
It uses recursion (or a stack) to keep track of visited nodes.
Key Idea:
Visit a node.
Recursively visit all unvisited adjacent nodes.
Backtrack when no more neighbors.
DFS Implementation in C (Using Adjacency Matrix)
#include <stdio.h>
#define SIZE 7
int visited[SIZE] = {0};
char vertex_data[SIZE] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int graph[SIZE][SIZE] = {0}; // Adjacency matrix
void addEdge(int u, int v) {
graph[u][v] = 1; // For directed graph
}
void dfs(int v) {
visited[v] = 1;
printf("%c ", vertex_data[v]);
for (int i = 0; i < SIZE; i++) {
if (graph[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
What is BFS (Breadth First Search)?
BFS visits all neighbors of a vertex before moving deeper.
It uses a queue to keep track of the next vertex to visit.
Key Idea:
Visit a node.
Add its unvisited neighbors to the queue.
Continue until the queue is empty.
BFS Implementation in C (Using Queue)
#include <stdio.h>
#define SIZE 7
int visited_bfs[SIZE] = {0};
int queue[SIZE], front = 0, rear = 0;
void enqueue(int v) {
queue[rear++] = v;
}
int dequeue() {
return queue[front++];
}
int isEmpty() {
return front == rear;
}
void bfs(int start) {
visited_bfs[start] = 1;
enqueue(start);
while (!isEmpty()) {
int v = dequeue();
printf("%c ", vertex_data[v]);
for (int i = 0; i < SIZE; i++) {
if (graph[v][i] == 1 && !visited_bfs[i]) {
enqueue(i);
visited_bfs[i] = 1;
}
}
}
}
Full Program (DFS + BFS in C)
#include <stdio.h>
#define SIZE 7
char vertex_data[SIZE] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int graph[SIZE][SIZE] = {0};
int visited[SIZE] = {0};
int visited_bfs[SIZE] = {0};
int queue[SIZE], front = 0, rear = 0;
// Add edge for directed graph
void addEdge(int u, int v) {
graph[u][v] = 1;
}
// DFS function
void dfs(int v) {
visited[v] = 1;
printf("%c ", vertex_data[v]);
for (int i = 0; i < SIZE; i++) {
if (graph[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
// Queue functions for BFS
void enqueue(int v) {
queue[rear++] = v;
}
int dequeue() {
return queue[front++];
}
int isEmpty() {
return front == rear;
}
// BFS function
void bfs(int start) {
visited_bfs[start] = 1;
enqueue(start);
while (!isEmpty()) {
int v = dequeue();
printf("%c ", vertex_data[v]);
for (int i = 0; i < SIZE; i++) {
if (graph[v][i] == 1 && !visited_bfs[i]) {
enqueue(i);
visited_bfs[i] = 1;
}
}
}
}
int main() {
// Creating directed graph (D -> A -> C, etc.)
addEdge(3, 0); // D -> A
addEdge(3, 4); // D -> E
addEdge(4, 0); // E -> A
addEdge(0, 2); // A -> C
addEdge(2, 5); // C -> F
addEdge(2, 6); // C -> G
addEdge(5, 1); // F -> B
addEdge(1, 2); // B -> C
printf("DFS traversal starting from D:\n");
dfs(3); // Vertex D (index 3)
printf("\n\nBFS traversal starting from D:\n");
bfs(3); // Vertex D (index 3)
return 0;
}
Output
DFS traversal starting from D:
D A C F B G E
BFS traversal starting from D:
D A E C F G B
DFS vs BFS – Comparison Table
Final Thought:
In C programming, mastering DFS and BFS allows you to work with graphs for networking, path finding, web crawling, and more. Choose DFS for depth logic and BFS for level-by-level search.
