苏州市城乡和建设局网站,网站建设到运营需要多少钱,网站设计常用字体,中文wordpress博客模板下载DFS#xff08;深度优先搜索#xff09;和BFS#xff08;广度优先搜索#xff09;是图论中常用的两种搜索方式。下面将介绍如何使用C语言实现DFS和BFS算法。
深度优先搜索#xff08;DFS#xff09;
DFS算法是一种用于遍历或搜索树或图的算法。 该算法从根结点开始深度优先搜索和BFS广度优先搜索是图论中常用的两种搜索方式。下面将介绍如何使用C语言实现DFS和BFS算法。
深度优先搜索DFS
DFS算法是一种用于遍历或搜索树或图的算法。 该算法从根结点开始尽可能深地搜索树的分支当遇到无法向下搜索的结点时回溯到父结点继续搜索下一分支。DFS算法可以使用递归函数或堆栈数据结构来实现。
下面是使用C语言实现DFS算法的代码
#include stdio.h
#define MAX_NODES 100int 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数组为0for (int i 0; i n; i) {visited[i] 0;}int start_node 0; // 从节点0开始遍历dfs(start_node);return 0;
}上述代码中首先定义了两个全局变量visited和graph用于标记节点是否被访问过和表示图的邻接矩阵。然后定义了一个递归函数dfs该函数从指定的节点开始遍历图标记该节点为已访问打印节点值然后继续遍历与该节点相邻的未访问节点。在main函数中初始化visited数组为0然后从节点0开始遍历图。
广度优先搜索BFS
BFS算法是一种用于遍历或搜索树或图的算法。该算法从根结点开始逐层遍历每个节点的所有子节点直到遇到目标结点或遍历完整个图。BFS算法可以使用队列数据结构来实现。
下面是使用C语言实现BFS算法的代码
#include stdio.h
#define MAX_NODES 100int 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数组为0for (int i 0; i n; i) {visited[i] 0;}int start_node 0; // 从节点0开始遍历bfs(start_node);return 0;
}上述代码中首先定义了两个全局变量visited和graph用于标记节点是否被访问过和表示图的邻接矩阵。然后定义了一个函数bfs该函数从指定的节点开始遍历图使用队列数据结构存储待访问节点标记已访问的节点打印节点值然后将与该节点相邻的未访问节点加入队列。在main函数中初始化visited数组为0然后从节点0开始遍历图。
总结
以上就是使用C语言实现DFS和BFS算法的代码这两种算法都是图论中常用的搜索算法可以通过递归函数或堆栈数据结构实现DFS算法可以通过队列数据结构实现BFS算法。
