DS - Graph Traversal Algorithms

calendarFeb 25, 2025 · 4 min read · Data Structures

In Data Structures (DS), BFS (Breadth-First Search) and DFS (Depth-First Search) are two fundamental graph traversal algorithms used to explore nodes in a graph or tree.

Breadth-First Search (BFS)

BFS explores a graph level by level, starting from a selected node and visiting all its neighbors before moving on to their neighbors.

How it works:

  1. Start from the initial node (source).
  2. Visit all directly connected nodes.
  3. Move to the next level and repeat until all nodes are visited.

Data Structure Used: Uses a Queue (FIFO) to keep track of nodes to visit next.

Use Cases:

  1. Shortest path in unweighted graphs (e.g., GPS navigation).
  2. Finding the closest friend in a social network.
  3. Web crawlers.

Program:

 1#include <stdio.h>
 2
 3// creating queue data structure using arrays
 4int queue[100];
 5
 6// defining pointers of the queue to perform pop and push
 7int front = 0, back = 0;
 8
 9// defining push operation on the queue
10void push(int var)
11{
12    queue[back] = var;
13    back++;
14}
15
16// defining pop operation on queue
17void pop()
18{
19    queue[front] = 0;
20    front++;
21}
22
23// creating a visited array to keep the track of visited nodes
24int visited[7] = {0};
25
26int main()
27{
28    // defining the number of total persons
29    int N = 6;
30
31    // adjacenty matrix representing graph
32    int graph[6][6] = {{0, 1, 1, 0, 0, 0},
33                       {1, 0, 1, 0, 0, 0},
34                       {1, 1, 0, 1, 1, 0},
35                       {0, 0, 1, 0, 0, 0},
36                       {0, 0, 1, 0, 0, 1},
37                       {0, 0, 0, 0, 1, 0}};
38
39    // front == back stands for empty queue
40    // until queue is not empty perfroming bfs
41
42    // adding a starting node in the list
43    push(1);
44    visited[0] = 1; // marking 1st node as visited
45    while (front != back)
46    {
47        int current = queue[front];
48
49        // printing current element
50        printf("%d ", current);
51
52        // popping the front element from the queue
53        pop();
54
55        for (int i = 0; i < 6; i++)
56        {
57            // adding non-visited connected nodes of the current node to the queue
58            if ((graph[current - 1][i] == 1) && (visited[i] == 0))
59            {
60                visited[i] = 1; // marking visisted
61                push(i + 1);
62            }
63        }
64    }
65    return 0;
66}


Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking.

How it works:

  1. Start from the initial node (source).
  2. Visit one neighbor and keep going deeper.
  3. Backtrack when you hit a dead end and explore the next neighbor.

Data Structure Used: Uses a Stack (LIFO), either explicitly or through recursion.

Use Cases:

  1. Solving puzzles (like mazes or Sudoku).
  2. Detecting cycles in a graph.
  3. Topological sorting.

Program:

 1#include <stdio.h>
 2
 3#define MAX_VERTICES 100
 4
 5// Function to perform Depth-First Search (DFS) traversal
 6void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int visited[MAX_VERTICES], int vertices, int start) {
 7    printf("%d ", start); // Print the current vertex
 8    visited[start] = 1;    // Mark the current vertex as visited
 9
10    // Visit all adjacent vertices
11    for (int i = 0; i < vertices; i++) {
12        if (graph[start][i] == 1 && !visited[i]) {
13            DFS(graph, visited, vertices, i);
14        }
15    }
16}
17
18int main() {
19    int vertices, edges;
20
21    // Input the number of vertices
22    printf("Enter the number of vertices: ");
23    scanf("%d", &vertices);
24
25    if (vertices <= 0 || vertices > MAX_VERTICES) {
26        printf("Invalid number of vertices. Exiting...\n");
27        return 1;
28    }
29
30    int graph[MAX_VERTICES][MAX_VERTICES] = {0}; // Initialize the adjacency matrix with zeros
31    int visited[MAX_VERTICES] = {0};             // Initialize the visited array with zeros
32
33    // Input the number of edges
34    printf("Enter the number of edges: ");
35    scanf("%d", &edges);
36
37    if (edges < 0 || edges > vertices * (vertices - 1)) {
38        printf("Invalid number of edges. Exiting...\n");
39        return 1;
40    }
41
42    // Input edges and construct the adjacency matrix
43    for (int i = 0; i < edges; i++) {
44        int start, end;
45        printf("Enter edge %d (start end): ", i + 1);
46        scanf("%d %d", &start, &end);
47
48        // Validate input vertices
49        if (start < 0 || start >= vertices || end < 0 || end >= vertices) {
50            printf("Invalid vertices. Try again.\n");
51            i--;
52            continue;
53        }
54
55        graph[start][end] = 1;
56        // For undirected graph, uncomment the following line:
57        // graph[end][start] = 1;
58    }
59
60    // Input the starting vertex for DFS traversal
61    int startVertex;
62    printf("Enter the starting vertex for DFS traversal: ");
63    scanf("%d", &startVertex);
64
65    if (startVertex < 0 || startVertex >= vertices) {
66        printf("Invalid starting vertex. Exiting...\n");
67        return 1;
68    }
69
70    printf("DFS Traversal Order: ");
71    DFS(graph, visited, vertices, startVertex);
72
73    return 0;
74}