C Graph Traversals 🎯

Welcome to our in-depth guide on C Graph Traversals! This lesson is designed for both beginners and intermediate learners. By the end of this tutorial, you'll have a solid understanding of graph traversal algorithms in C, their implementation, and their practical applications. Let's dive in!

What are Graph Traversals? 📝

Graph traversals are techniques used to visit each node (vertex) in a graph and its adjacent nodes. They are essential in solving various problems, such as finding the shortest path, detecting cycles, or finding connected components.

Graph Representation in C 💡

In C, we usually represent graphs using adjacency matrices and adjacency lists. In this tutorial, we will focus on adjacency lists.

Depth-First Search (DFS) 🎯

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

DFS Recursive Implementation 💡

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

int visited[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];

void DFSUtil(int v, int array[], int size) {
    visited[v] = 1;
    printf("Visited vertex %d\n", v);
    array[v] = 1; // Mark the current vertex as visited in the result array

    for (int i = 0; i < size; i++) {
        if (!visited[i] && graph[v][i] == 1)
            DFSUtil(i, array, size);
    }
}

void DFSTraversal(int graph[][MAX_VERTICES], int vertices) {
    int array[vertices];

    for (int i = 0; i < vertices; i++)
        visited[i] = 0;

    for (int i = 0; i < vertices; i++) {
        if (!visited[i])
            DFSUtil(i, array, vertices);
    }
}

Quiz: What does the DFSUtil function do in the given code?

DFS Iterative Implementation 💡

DFS can also be implemented iteratively using a stack.

#include <stdio.h>
#include <stdlib.h>
#include <stack>

#define MAX_VERTICES 100

int visited[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];

void DFS(int v, int array[], int size) {
    std::stack<int> stack;

    visited[v] = 1;
    printf("Visited vertex %d\n", v);
    array[v] = 1; // Mark the current vertex as visited in the result array
    stack.push(v);

    while (!stack.empty()) {
        int top = stack.top();
        stack.pop();

        for (int i = 0; i < size; i++) {
            if (!visited[i] && graph[top][i] == 1) {
                stack.push(i);
                visited[i] = 1;
                printf("Visited vertex %d\n", i);
                array[i] = 1;
                break;
            }
        }
    }
}

void DFSTraversal(int graph[][MAX_VERTICES], int vertices) {
    int array[vertices];

    for (int i = 0; i < vertices; i++)
        visited[i] = 0;

    for (int i = 0; i < vertices; i++) {
        if (!visited[i])
            DFS(i, array, vertices);
    }
}

Breadth-First Search (BFS) 🎯

BFS is a graph traversal algorithm that explores all the vertices at a given depth level before moving on to the next level.

BFS Implementation 💡

#include <stdio.h>
#include <stdlib.h>
#include <queue>

#define MAX_VERTICES 100

int visited[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];

void BFSUtil(int v, int array[], int size) {
    std::queue<int> queue;

    visited[v] = 1;
    printf("Visited vertex %d\n", v);
    array[v] = 1; // Mark the current vertex as visited in the result array
    queue.push(v);

    while (!queue.empty()) {
        int front = queue.front();
        queue.pop();

        for (int i = 0; i < size; i++) {
            if (!visited[i] && graph[front][i] == 1) {
                visited[i] = 1;
                printf("Visited vertex %d\n", i);
                array[i] = 1;
                queue.push(i);
            }
        }
    }
}

void BFSTraversal(int graph[][MAX_VERTICES], int vertices) {
    int array[vertices];

    for (int i = 0; i < vertices; i++)
        visited[i] = 0;

    for (int i = 0; i < vertices; i++) {
        if (!visited[i])
            BFSUtil(i, array, vertices);
    }
}

Conclusion 🎯

Understanding graph traversals is essential for solving complex problems in graph theory. We've covered the basics of DFS and BFS in C, providing both recursive and iterative implementations. Keep practicing these techniques to master graph traversal algorithms!