```html

Graph Traversal: Breadth-First Search (BFS) and Depth-First Search (DFS) in C

Graphs are fundamental non-linear data structures used to model real-world problems, from social networks and road maps to circuit design and computer networks. Understanding how to traverse these complex structures is crucial for solving a myriad of computational problems. In this 176th installment of our C Language Series, we'll dive deep into two of the most foundational graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS), complete with C implementations and explanations.

What is Graph Traversal?

Graph traversal refers to the process of visiting (checking and/or updating) each vertex in a graph. The goal is to ensure that every vertex is visited exactly once, in a systematic manner. Traversal algorithms are essential for tasks like:

• Finding a path between two nodes.
• Detecting cycles in a graph.
• Finding connected components.
• Solving maze problems.
• Network broadcasting.

Let's explore BFS and DFS, their mechanics, and their practical applications.

Breadth-First Search (BFS)

BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Think of BFS as ripples spreading out in a pond. When you drop a pebble, the ripples spread out in expanding circles, visiting all points at one distance before moving to points at a greater distance.

How BFS Works (High-Level Algorithm):

1. Pick a starting node, mark it as visited, and add it to a queue.
2. While the queue is not empty:
   1. Dequeue a node.
   2. Process the dequeued node (e.g., print it).
   3. Add all unvisited neighbors of the dequeued node to the queue and mark them as visited.

BFS guarantees finding the shortest path in terms of the number of edges between the source node and any other reachable node in an unweighted graph.

When to use BFS:

• Finding the shortest path in an unweighted graph.
• Finding all nodes within a connected component.
• Crawl web pages (e.g., search engine indexers).
• Social networking "friend of a friend" searches.

C Implementation of BFS

To implement BFS in C, we need a way to represent the graph, a queue data structure, and an array to keep track of visited nodes. We'll use an adjacency list for graph representation due to its efficiency for sparse graphs.

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

#define MAX_NODES 100

// --- Graph Representation (Adjacency List) ---
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

struct AdjList {
    struct AdjListNode *head; // Pointer to head of adjacency list
};

struct Graph {
    int V; // Number of vertices
    struct AdjList* array;
};

// Function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// Function to add an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add an edge from src to dest
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Add an edge from dest to src (for undirected graph)
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// --- Queue Implementation for BFS ---
struct Queue {
    int items[MAX_NODES];
    int front;
    int rear;
};

struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

int isEmpty(struct Queue* q) {
    if (q->rear == -1)
        return 1;
    else
        return 0;
}

void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX_NODES - 1)
        printf("\nQueue is Full!");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(struct Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1; // Reset queue
        }
    }
    return item;
}

// --- BFS Algorithm ---
void bfs(struct Graph* graph, int startVertex) {
    struct Queue* q = createQueue();
    int visited[MAX_NODES]; // Array to keep track of visited nodes

    for (int i = 0; i < graph->V; i++)
        visited[i] = 0; // Initialize all nodes as not visited

    visited[startVertex] = 1;
    enqueue(q, startVertex);

    printf("BFS Traversal starting from vertex %d: ", startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);

        struct AdjListNode* temp = graph->array[currentVertex].head;
        while (temp) {
            int adjVertex = temp->dest;
            if (visited[adjVertex] == 0) {
                visited[adjVertex] = 1;
                enqueue(q, adjVertex);
            }
            temp = temp->next;
        }
    }
    printf("\n");
    free(q); // Free the queue
}

// --- Main function to test BFS ---
int main() {
    int V = 5; // Number of vertices
    struct Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);

    bfs(graph, 0); // Start BFS from vertex 0

    // Free graph memory
    for (int i = 0; i < V; ++i) {
        struct AdjListNode* current = graph->array[i].head;
        while (current) {
            struct AdjListNode* next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->array);
    free(graph);

    return 0;
}

BFS Time and Space Complexity:

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. This is because every vertex and every edge will be visited at most once.
• Space Complexity: O(V) for the queue (in the worst case, all vertices might be in the queue) and O(V) for the visited array.

Depth-First Search (DFS)

DFS is another fundamental graph traversal algorithm. It explores as far as possible along each branch before backtracking. It uses a stack data structure (implicitly via recursion or explicitly with an iterative approach).

Imagine navigating a maze: you pick a path and keep going as deep as you can until you hit a dead end. When you can't go any further, you backtrack to the last point where you had an alternative path and try that one.

How DFS Works (High-Level Algorithm - Recursive):

1. Pick a starting node, mark it as visited, and process it.
2. For each unvisited neighbor of the current node:
   1. Recursively call DFS on that neighbor.

When to use DFS:

• Detecting cycles in a graph.
• Topological sorting.
• Finding connected components.
• Pathfinding (not necessarily the shortest).
• Solving puzzles with only one solution, like mazes.

C Implementation of DFS

DFS is naturally implemented using recursion due to its inherent backtracking nature. Similar to BFS, we need a graph representation and a way to track visited nodes.

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

#define MAX_NODES 100

// --- Graph Representation (Adjacency List - same as BFS) ---
// (Refer to the BFS section for these struct definitions and helper functions)
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

struct AdjList {
    struct AdjListNode *head;
};

struct Graph {
    int V;
    struct AdjList* array;
};

struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// --- DFS Algorithm ---
void DFSUtil(struct Graph* graph, int v, int visited[]) {
    visited[v] = 1; // Mark the current node as visited
    printf("%d ", v); // Process (print) the current node

    struct AdjListNode* adjList = graph->array[v].head;
    while (adjList != NULL) {
        int connectedVertex = adjList->dest;
        if (visited[connectedVertex] == 0) {
            DFSUtil(graph, connectedVertex, visited); // Recur for all unvisited adjacent vertices
        }
        adjList = adjList->next;
    }
}

void dfs(struct Graph* graph, int startVertex) {
    int visited[MAX_NODES]; // Array to keep track of visited nodes

    for (int i = 0; i < graph->V; i++)
        visited[i] = 0; // Initialize all nodes as not visited

    printf("DFS Traversal starting from vertex %d: ", startVertex);
    DFSUtil(graph, startVertex, visited);
    printf("\n");
}

// --- Main function to test DFS ---
int main() {
    int V = 5; // Number of vertices
    struct Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);

    dfs(graph, 0); // Start DFS from vertex 0

    // Free graph memory
    for (int i = 0; i < V; ++i) {
        struct AdjListNode* current = graph->array[i].head;
        while (current) {
            struct AdjListNode* next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->array);
    free(graph);

    return 0;
}

DFS Time and Space Complexity:

• Time Complexity: O(V + E) for adjacency list, similar to BFS. Each vertex and edge is visited once.
• Space Complexity: O(V) for the recursion stack (in the worst case, a skewed graph can lead to a recursion depth equal to V) and O(V) for the visited array.

BFS vs. DFS: Key Differences

While both BFS and DFS are powerful graph traversal algorithms, they differ significantly in their approach and applications.

Feature	Breadth-First Search (BFS)	Depth-First Search (DFS)
Traversal Order	Explores level by level (horizontal). Visits all immediate neighbors first, then their neighbors, and so on.	Explores as deep as possible along each branch before backtracking (vertical).
Data Structure	Uses a Queue to store nodes to visit.	Uses a Stack (explicitly or implicitly via recursion) to store nodes to visit/backtrack.
Shortest Path	Guarantees finding the shortest path in an unweighted graph (by number of edges).	Does not guarantee finding the shortest path.
Memory Usage	Can require more memory for wide graphs (many nodes at the same level) as the queue can grow large.	Can require more memory for deep graphs (long paths) due to the recursion stack.
Applications	Shortest path in unweighted graphs, network broadcasting, finding connected components.	Cycle detection, topological sorting, pathfinding, maze solving, strongly connected components.

Conclusion

BFS and DFS are fundamental algorithms that form the bedrock of many advanced graph algorithms and applications. Understanding their distinct traversal patterns, underlying data structures, and use cases is vital for any programmer working with graphs. Whether you're finding the quickest route, analyzing network connectivity, or solving complex puzzles, these two algorithms are indispensable tools in your computational arsenal. Practice implementing them, experiment with different graph structures, and observe how their traversal paths differ to truly master graph traversal.

```