图的深度优先遍历和广度优先遍历合在一起的c语言代码
时间: 2023-09-04 09:14:13 浏览: 99
图的深度优先遍历与广度优先遍历(C语言实现)
5星 · 资源好评率100%
以下是一个将深度优先遍历和广度优先遍历合并在一起的图遍历代码(使用C语言实现):
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 1000
// 定义图结构
typedef struct Graph {
int V; // 节点数
bool adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示边
} Graph;
// 初始化图
void init_graph(Graph *g, int V) {
g->V = V;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
g->adj[i][j] = false;
}
}
}
// 添加边
void add_edge(Graph *g, int u, int v) {
g->adj[u][v] = true;
g->adj[v][u] = true;
}
// 深度优先遍历
void dfs(Graph *g, int v, bool visited[]) {
visited[v] = true;
printf("%d ", v);
for (int i = 0; i < g->V; i++) {
if (g->adj[v][i] && !visited[i]) {
dfs(g, i, visited);
}
}
}
// 广度优先遍历
void bfs(Graph *g, int v, bool visited[]) {
int queue[MAX_VERTICES], front = -1, rear = -1;
visited[v] = true;
queue[++rear] = v;
while (front != rear) {
v = queue[++front];
printf("%d ", v);
for (int i = 0; i < g->V; i++) {
if (g->adj[v][i] && !visited[i]) {
visited[i] = true;
queue[++rear] = i;
}
}
}
}
// 组合深度优先遍历和广度优先遍历
void dfs_bfs(Graph *g, int v) {
bool visited[MAX_VERTICES] = {false};
dfs(g, v, visited);
for (int i = 0; i < g->V; i++) {
if (!visited[i]) {
bfs(g, i, visited);
}
}
}
int main() {
Graph g;
init_graph(&g, 6);
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 2);
add_edge(&g, 1, 3);
add_edge(&g, 2, 3);
add_edge(&g, 3, 4);
add_edge(&g, 4, 5);
dfs_bfs(&g, 0);
return 0;
}
```
这个代码中的 Graph 结构使用邻接矩阵来表示图,其中 adj[i][j] 表示节点 i 和节点 j 之间是否有边。我们可以使用 init_graph 和 add_edge 函数来初始化图和添加边。dfs 和 bfs 函数分别实现了深度优先遍历和广度优先遍历。最后,dfs_bfs 函数将深度优先遍历和广度优先遍历组合在一起,输出遍历过的节点。在主函数中,我们创建了一个包含 6 个节点的图,并调用 dfs_bfs 函数来遍历图中的节点。
阅读全文