Graph traversal is a fundamental operation in computer science, used in networking, AI, and pathfinding. Breadth-First Search (BFS) explores neighbors level by level, making it ideal for finding the shortest path in unweighted graphs. Depth-First Search (DFS) explores as far as possible along each branch before backtracking, which is useful for connectivity, topological sorting, and cycle detection. Understanding both methods is essential for working with graphs efficiently.
Understanding the Problem
Traversing a graph requires visiting all nodes while avoiding revisiting the same vertex. BFS uses a queue to explore vertices level by level, while DFS uses recursion or a stack to go deep into each branch. Implementing both methods involves careful management of adjacency representations, visited tracking, and correct iteration over neighbors.
Program 1: Breadth-First Search (BFS)
This program demonstrates BFS on a graph represented by an adjacency matrix. BFS explores all neighbors of the current vertex before moving to the next level, ensuring a level-by-level traversal.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct Queue {
int items[MAX];
int front, rear;
} Queue;
void initQueue(Queue *q) {
q->front = q->rear = -1;
}
int isEmpty(Queue *q) {
return q->front == -1;
}
void enqueue(Queue *q, int value) {
if (q->rear == MAX - 1) return;
if (isEmpty(q)) q->front = 0;
q->items[++q->rear] = value;
}
int dequeue(Queue *q) {
if (isEmpty(q)) return -1;
int val = q->items[q->front];
if (q->front >= q->rear) q->front = q->rear = -1;
else q->front++;
return val;
}
void BFS(int graph[MAX][MAX], int start, int n) {
int visited[MAX] = {0};
Queue q;
initQueue(&q);
visited[start] = 1;
enqueue(&q, start);
printf("BFS Traversal: ");
while (!isEmpty(&q)) {
int vertex = dequeue(&q);
printf("%d ", vertex);
for (int i = 0; i < n; i++) {
if (graph[vertex][i] && !visited[i]) {
visited[i] = 1;
enqueue(&q, i);
}
}
}
printf("\n");
}
int main() {
int n = 5;
int graph[MAX][MAX] = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,0},
{0,1,0,0,1},
{0,1,0,1,0}
};
BFS(graph, 0, n);
return 0;
}In BFS, a queue ensures that nodes are visited in the correct level order. The visited array prevents revisiting nodes, making the traversal efficient and avoiding infinite loops in cyclic graphs.
Program 2: Breadth-First Search (BFS) Using Adjacency List
This program demonstrates BFS on a graph represented by adjacency lists. A queue ensures level-by-level traversal, and the visited array prevents revisiting nodes.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node *next;
} Node;
typedef struct Graph {
int numVertices;
Node **adjLists;
} Graph;
typedef struct Queue {
int *items;
int front, rear, capacity;
} Queue;
// Create a new node for adjacency list
Node* createNode(int v) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create a graph with n vertices
Graph* createGraph(int vertices) {
Graph *graph = (Graph*) malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = (Node**) malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// Add edge to graph (undirected)
void addEdge(Graph *graph, int src, int dest) {
Node *newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// Queue functions
Queue* createQueue(int capacity) {
Queue *q = (Queue*) malloc(sizeof(Queue));
q->items = (int*) malloc(capacity * sizeof(int));
q->front = 0;
q->rear = -1;
q->capacity = capacity;
return q;
}
int isEmpty(Queue *q) {
return q->rear < q->front;
}
void enqueue(Queue *q, int value) {
q->items[++q->rear] = value;
}
int dequeue(Queue *q) {
if (isEmpty(q)) return -1;
return q->items[q->front++];
}
// BFS traversal
void BFS(Graph *graph, int start) {
int *visited = (int*) calloc(graph->numVertices, sizeof(int));
Queue *q = createQueue(graph->numVertices);
visited[start] = 1;
enqueue(q, start);
printf("BFS Traversal (Adjacency List): ");
while (!isEmpty(q)) {
int vertex = dequeue(q);
printf("%d ", vertex);
Node *temp = graph->adjLists[vertex];
while (temp) {
if (!visited[temp->vertex]) {
visited[temp->vertex] = 1;
enqueue(q, temp->vertex);
}
temp = temp->next;
}
}
printf("\n");
free(visited);
free(q->items);
free(q);
}
int main() {
int n = 5;
Graph *graph = createGraph(n);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
BFS(graph, 0);
return 0;
}This BFS implementation using adjacency lists is efficient for sparse graphs. Each vertex’s neighbors are stored in a linked list, avoiding the need for a full adjacency matrix.
Program 3: Depth-First Search (DFS)
This program demonstrates DFS using recursion on a graph represented by an adjacency matrix. DFS explores as far as possible along each branch before backtracking.
#include <stdio.h>
#define MAX 100
void DFS(int graph[MAX][MAX], int vertex, int visited[MAX], int n) {
visited[vertex] = 1;
printf("%d ", vertex);
for (int i = 0; i < n; i++) {
if (graph[vertex][i] && !visited[i])
DFS(graph, i, visited, n);
}
}
int main() {
int n = 5;
int graph[MAX][MAX] = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,0},
{0,1,0,0,1},
{0,1,0,1,0}
};
int visited[MAX] = {0};
printf("DFS Traversal: ");
DFS(graph, 0, visited, n);
printf("\n");
return 0;
}DFS uses recursion to explore each branch fully before moving to the next neighbor. The call stack naturally keeps track of the path, eliminating the need for an explicit stack structure and making the implementation elegant and straightforward.
Program 4: Depth-First Search (DFS) Using Adjacency List
This program demonstrates DFS using recursion on a graph represented by adjacency lists. It explores each branch fully before backtracking.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node *next;
} Node;
typedef struct Graph {
int numVertices;
Node **adjLists;
} Graph;
// Create a new node
Node* createNode(int v) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create a graph with n vertices
Graph* createGraph(int vertices) {
Graph *graph = (Graph*) malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = (Node**) malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// Add undirected edge
void addEdge(Graph *graph, int src, int dest) {
Node *newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// DFS traversal
void DFS(Graph *graph, int vertex, int *visited) {
visited[vertex] = 1;
printf("%d ", vertex);
Node *temp = graph->adjLists[vertex];
while (temp) {
if (!visited[temp->vertex])
DFS(graph, temp->vertex, visited);
temp = temp->next;
}
}
int main() {
int n = 5;
Graph *graph = createGraph(n);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
int *visited = (int*) calloc(n, sizeof(int));
printf("DFS Traversal (Adjacency List): ");
DFS(graph, 0, visited);
printf("\n");
free(visited);
return 0;
}DFS with adjacency lists is memory-efficient for sparse graphs. Using recursion simplifies the process of exploring all neighbors and backtracking automatically, while adjacency lists reduce unnecessary memory usage compared to adjacency matrices.
FAQs
Q1: When to use BFS vs DFS?
Use BFS to find the shortest path in unweighted graphs. Use DFS for connectivity, cycle detection, or topological sorting.
Q2: Can these algorithms handle disconnected graphs?
Yes, but you must run BFS/DFS from all unvisited vertices to cover disconnected components.
Q3: What is the time complexity?
Both BFS and DFS have O(V + E), where V is vertices and E is edges.
Q4: Which data structures are used?
BFS uses a queue, DFS uses recursion (stack) or an explicit stack.
Conclusion
BFS and DFS are fundamental graph traversal techniques. BFS is level-wise, useful for shortest paths, while DFS is depth-wise, useful for connectivity and cycle detection. Mastering both methods is essential for tackling advanced graph problems in programming and real-world applications.
References & Additional Resources
A curated list of books and online resources providing both theoretical foundations and practical examples for understanding graph traversal algorithms (BFS and DFS) and their implementation in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language, 2nd Edition. Prentice Hall – Classic reference on C fundamentals, including pointers, memory, and algorithm implementation.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Covers graph representations, traversal algorithms, and their C implementations.
- GeeksforGeeks: Breadth-First Search (BFS) – Step-by-step explanation and C code examples for BFS traversal.
- GeeksforGeeks: Depth-First Search (DFS) – Comprehensive guide and C implementation examples for DFS traversal.
