深入探索图算法：用C语言实现BFS和DFS

短命女 2023-10-14 22:01 8阅读 0赞

## 深入探索图算法：用C语言实现BFS和DFS ##

图算法是计算机科学中一个重要且有趣的领域，它们在解决许多现实世界的问题时发挥着关键作用。本篇博客将介绍两种常见的图算法：广度优先搜索（BFS）和深度优先搜索（DFS），并提供在C语言中的实现示例。

### 广度优先搜索（BFS） ###

广度优先搜索是一种用于图遍历的算法，它从起始节点开始逐层遍历图的节点，直到找到目标节点或遍历完整个图。下面是BFS算法的C语言实现示例：

#include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    #define MAX_VERTICES 100
    
    typedef struct {
        int data[MAX_VERTICES];
        int front, rear;
    } Queue;
    
    void initQueue(Queue *q) {
        q->front = q->rear = -1;
    }
    
    bool isEmpty(Queue *q) {
        return q->front == -1;
    }
    
    void enqueue(Queue *q, int value) {
        if (isEmpty(q)) {
            q->front = q->rear = 0;
        } else {
            q->rear++;
        }
        q->data[q->rear] = value;
    }
    
    int dequeue(Queue *q) {
        int value = q->data[q->front];
        if (q->front == q->rear) {
            q->front = q->rear = -1;
        } else {
            q->front++;
        }
        return value;
    }
    
    void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int start) {
        bool visited[MAX_VERTICES] = { false };
        Queue q;
        initQueue(&q);
    
        visited[start] = true;
        enqueue(&q, start);
    
        while (!isEmpty(&q)) {
            int vertex = dequeue(&q);
            printf("%d ", vertex);
    
            for (int i = 0; i < vertices; i++) {
                if (graph[vertex][i] && !visited[i]) {
                    visited[i] = true;
                    enqueue(&q, i);
                }
            }
        }
    }
    
    int main() {
        int vertices, edges, start;
        printf("Enter the number of vertices: ");
        scanf("%d", &vertices);
        printf("Enter the number of edges: ");
        scanf("%d", &edges);
    
        int graph[MAX_VERTICES][MAX_VERTICES] = { 0 };
    
        printf("Enter the edges (format: u v):\n");
        for (int i = 0; i < edges; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            graph[u][v] = graph[v][u] = 1;
        }
    
        printf("Enter the starting vertex: ");
        scanf("%d", &start);
    
        printf("BFS traversal starting from vertex %d: ", start);
        BFS(graph, vertices, start);
    
        return 0;
    }

### 深度优先搜索（DFS） ###

深度优先搜索是另一种图遍历算法，它沿着图的深度尽可能远地探索节点，然后回溯到之前的节点继续探索。下面是DFS算法的C语言实现示例：

#include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    #define MAX_VERTICES 100
    
    typedef struct {
        int data[MAX_VERTICES];
        int top;
    } Stack;
    
    void initStack(Stack *s) {
        s->top = -1;
    }
    
    bool isEmpty(Stack *s) {
        return s->top == -1;
    }
    
    void push(Stack *s, int value) {
        s->data[++s->top] = value;
    }
    
    int pop(Stack *s) {
        return s->data[s->top--];
    }
    
    void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int vertex, bool visited[MAX_VERTICES]) {
        printf("%d ", vertex);
        visited[vertex] = true;
    
        for (int i = 0; i < vertices; i++) {
            if (graph[vertex][i] && !visited[i]) {
                DFS(graph, vertices, i, visited);
            }
        }
    }
    
    int main() {
        int vertices, edges, start;
        printf("Enter the number of vertices: ");
        scanf("%d", &vertices);
        printf("Enter the number of edges: ");
        scanf("%d", &edges);
    
        int graph[MAX_VERTICES][MAX_VERTICES] = { 0 };
    
        printf("Enter the edges (format: u v):\n");
        for (int i = 0; i < edges; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            graph[u][v] = graph[v][u] = 1;
        }
    
        printf("Enter the starting vertex: ");
        scanf("%d", &start);
    
        bool visited[MAX_VERTICES] = { false };
        printf("DFS traversal starting from vertex %d: ", start);
        DFS(graph, vertices, start, visited);
    
        return 0;
    }

### 总结 ###

本篇博客介绍了图算法中的两个重要概念：广度优先搜索（BFS）和深度优先搜索（DFS）。通过C语言实现的示例代码，您可以更好地理解这两种算法的工作原理和用途。图算法在社交网络分析、路径规划、游戏开发等领域具有广泛的应用，深入理解这些算法将有助于您解决各种实际问题。

希望本文对您学习图算法和C语言编程有所帮助！如果您有任何问题或建议，请随时在评论区留言。