C Language Algorithms: Depth-First Search and Breadth-First Search

In computer science, a graph is an important data structure. Graph traversal is a fundamental operation for processing graphs, and Depth-First Search (DFS) and Breadth-First Search (BFS) are two commonly used graph traversal algorithms. This article will provide a detailed introduction to these two algorithms along with corresponding C language code examples.

1. Depth-First Search (DFS)

1.1 Overview

Depth-First Search is an algorithm used for traversing or searching trees or graphs. It starts at the root node and explores each branch to its deepest point before backtracking to the previous node to continue exploring other branches.

1.2 Algorithm Steps

  1. Start visiting from the initial node.
  2. Mark the node as visited.
  3. For each unvisited adjacent node, recursively perform steps 1-3.
  4. If there are no unvisited adjacent nodes, backtrack to the previous node.

1.3 C Language Implementation

Below is a C language code example implementing DFS using recursion:

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100

typedef struct Graph {
    int vertices;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

void initGraph(Graph* g, int vertices) {
    g->vertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

void addEdge(Graph* g, int start, int end) {
    g->adjMatrix[start][end] = 1;
    g->adjMatrix[end][start] = 1; // Undirected graph
}

void DFS(Graph* g, int vertex, int visited[]) {
    visited[vertex] = 1; // Mark as visited
    printf("%d ", vertex); // Output current vertex
    for (int i = 0; i < g->vertices; i++) {
        if (g->adjMatrix[vertex][i] == 1 && !visited[i]) { // If there is an edge and not visited
            DFS(g, i, visited);
        }
    }
}

int main() {
    Graph graph;
    initGraph(&graph, 5);
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 2, 4);
    printf("Depth-First Search Result: ");
    int visited[MAX_VERTICES] = {0}; // Initialize all vertices as unvisited
    DFS(&graph, 0, visited); // Start DFS from vertex 0
    return EXIT_SUCCESS;
}

1.4 Example Explanation

  • <span>initGraph</span> function initializes the graph structure and sets up the adjacency matrix.
  • <span>addEdge</span> function adds an undirected edge.
  • <span>DFS</span> function implements the recursive depth-first traversal and prints each visited vertex.

2. Breadth-First Search (BFS)

2.1 Overview

Breadth-First Search is a method for traversing or searching trees or graphs. It starts at the root node and explores all neighboring nodes before expanding outward layer by layer. This means it first explores the closest layer to the starting node, then the next layer, and so on.

2.2 Algorithm Steps

  1. Enqueue the starting node and mark it as visited.
  2. While the queue is not empty:
  • Dequeue an element and process it.
  • Enqueue all unvisited adjacent nodes and mark them as visited.

2.3 C Language Implementation

Below is a C language code example implementing BFS using a queue:

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES    100
#define QUEUE_SIZE       MAX_VERTICES

typedef struct Queue {
    int items[QUEUE_SIZE];
    int front;
    int rear;
} Queue;

typedef struct Graph {
    int vertices;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(Queue *q) {
    return q->rear == QUEUE_SIZE - 1 ? -1 : q->rear + 2 == q->front ? -2 : -3;
}

int isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if (isFull(q) == -3) printf("Queue is full\n");
    else {
        if (q->front == -1) q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -9999;
    } else {
        return q->items[q->front++];
        if (q->front > q->rear) initQueue(q);
    }
}

void initGraph(Graph* g, int vertices) {
    g->vertices = vertices;
    for (int i = 0; i < vertices; i++)
        for (int j = 0; j < vertices; j++)
            g->adjMatrix[i][j] = 0;
}

void addEdge(Graph* g, int start, int end) {
    g->adjMatrix[start][end] = g->adjMatrix[end][start] = true;
}

void BFS(Graph* graph, int startVertex) {
    int visited[MAX_VERTICES] = {false};
    visited[startVertex] = true;
    printf("Breadth-First Search Result: ");
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, startVertex);
    while (!isEmpty(&queue)) {
        int currentVertex = dequeue(&queue);
        printf("%d ", currentVertex);
        for (int v = 0; v < graph->vertices; ++v) {
            if (graph->adjMatrix[currentVertex][v] == true && !visited[v]) {
                visited[v] = true;
                enqueue(&queue, v);
            }
        }
    }
    printf("\n");
}

int main() {
    Graph graph;
    initGraph(&graph, 5);
    addEdge(&graph, 0, 4);
    addEdge(&graph, 4, 3);
    addEdge(&graph, 4, 2);
    addEdge(&graph, 4, 5);
    BFS(&graph, 4);
    return EXIT_SUCCESS;
}

2.4 Example Explanation

  • <span>initGraph</span> and <span>addEdge</span> functions are the same as in the DFS section, used for initializing and constructing the graph structure.
  • <span>BFS</span> function performs breadth-first traversal using loops and queues, printing each processed vertex.

3. Conclusion

This article introduced two fundamental and important graph traversal algorithms: Depth-First Search and Breadth-First Search. By understanding these basics, you can better solve practical problems such as pathfinding and network flow analysis. In practical applications, choosing the appropriate method based on specific needs will greatly enhance efficiency. I hope this article helps you gain a deeper understanding of these two classic algorithms!

Leave a Comment