C语言实现DFS和BFS

DFS（深度优先搜索）和BFS（广度优先搜索）是图论中常用的两种搜索方式。下面将介绍如何使用C语言实现DFS和BFS算法。

深度优先搜索（DFS）

DFS算法是一种用于遍历或搜索树或图的算法。 该算法从根结点开始，尽可能深地搜索树的分支，当遇到无法向下搜索的结点时，回溯到父结点，继续搜索下一分支。DFS算法可以使用递归函数或堆栈数据结构来实现。

下面是使用C语言实现DFS算法的代码：

#include 
#define MAX_NODES 100

int visited[MAX_NODES]; // 标记节点是否被访问过
int graph[MAX_NODES][MAX_NODES]; // 图的邻接矩阵
int n; // 图的大小

void dfs(int node) {
    visited[node] = 1;
    printf("%d ", node);

    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i);
        }
    }
}

int main() {
    // 假设图的大小为n，邻接矩阵为graph
    // 初始化visited数组为0
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    int start_node = 0; // 从节点0开始遍历
    dfs(start_node);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

上述代码中，首先定义了两个全局变量：visited和graph，用于标记节点是否被访问过和表示图的邻接矩阵。然后定义了一个递归函数dfs，该函数从指定的节点开始遍历图，标记该节点为已访问，打印节点值，然后继续遍历与该节点相邻的未访问节点。在main函数中，初始化visited数组为0，然后从节点0开始遍历图。

广度优先搜索（BFS）

BFS算法是一种用于遍历或搜索树或图的算法。该算法从根结点开始，逐层遍历每个节点的所有子节点，直到遇到目标结点或遍历完整个图。BFS算法可以使用队列数据结构来实现。

下面是使用C语言实现BFS算法的代码：

#include 
#define MAX_NODES 100

int visited[MAX_NODES]; // 标记节点是否被访问过
int graph[MAX_NODES][MAX_NODES]; // 图的邻接矩阵
int n; // 图的大小

void bfs(int start_node) {
    int queue[MAX_NODES]; // 队列用于存储待访问节点
    int front = 0, rear = 0;

    queue[rear++] = start_node;
    visited[start_node] = 1;

    while (front < rear) {
        int curr_node = queue[front++];
        printf("%d ", curr_node);

        for (int i = 0; i < n; i++) {
            if (graph[curr_node][i] && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    // 假设图的大小为n，邻接矩阵为graph
    // 初始化visited数组为0
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    int start_node = 0; // 从节点0开始遍历
    bfs(start_node);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

上述代码中，首先定义了两个全局变量：visited和graph，用于标记节点是否被访问过和表示图的邻接矩阵。然后定义了一个函数bfs，该函数从指定的节点开始遍历图，使用队列数据结构存储待访问节点，标记已访问的节点，打印节点值，然后将与该节点相邻的未访问节点加入队列。在main函数中，初始化visited数组为0，然后从节点0开始遍历图。

总结：

以上就是使用C语言实现DFS和BFS算法的代码，这两种算法都是图论中常用的搜索算法，可以通过递归函数或堆栈数据结构实现DFS算法，可以通过队列数据结构实现BFS算法。