建立的无向图,实现图的深度优先遍历和广度优先遍历,并输出相应遍历结果用C语言
时间: 2023-11-22 10:53:23 浏览: 101
C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
5星 · 资源好评率100%
下面是一个简单的无向图的深度优先遍历和广度优先遍历的C语言实现。在代码中,我们使用了邻接矩阵来表示无向图。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int adj_matrix[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int queue[MAX_VERTICES];
int front = -1, rear = -1;
void add_edge(int u, int v) {
adj_matrix[u][v] = 1;
adj_matrix[v][u] = 1;
}
void dfs(int v, int vertices) {
int i;
visited[v] = 1;
printf("%d ", v);
for (i = 0; i < vertices; i++) {
if (adj_matrix[v][i] == 1 && !visited[i]) {
dfs(i, vertices);
}
}
}
void bfs(int v, int vertices) {
int i, u;
visited[v] = 1;
printf("%d ", v);
queue[++rear] = v;
while (front != rear) {
u = queue[++front];
for (i = 0; i < vertices; i++) {
if (adj_matrix[u][i] == 1 && !visited[i]) {
visited[i] = 1;
printf("%d ", i);
queue[++rear] = i;
}
}
}
}
int main() {
int vertices, edges;
int u, v, i;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);
printf("Enter the number of edges: ");
scanf("%d", &edges);
for (i = 0; i < edges; i++) {
printf("Enter edge %d: ", i + 1);
scanf("%d %d", &u, &v);
add_edge(u, v);
}
printf("Depth First Traversal: ");
dfs(0, vertices);
printf("\nBreadth First Traversal: ");
bfs(0, vertices);
return 0;
}
```
在这个程序中,我们首先定义了一个邻接矩阵 `adj_matrix` 来表示无向图。然后,我们实现了 `add_edge` 函数来向图中添加边。接下来,我们实现了深度优先遍历 `dfs` 和广度优先遍历 `bfs` 函数。在遍历时,我们使用了 `visited` 数组来跟踪哪些节点已经被访问过,以避免重复访问。最后,我们在 `main` 函数中读取输入并调用 `dfs` 和 `bfs` 函数来进行遍历。
阅读全文