C语言实现深度优先遍历和广度优先遍历
时间: 2023-12-12 15:33:26 浏览: 108
图的深度、广度优先遍历(c语言)
5星 · 资源好评率100%
以下是C语言实现深度优先遍历和广度优先遍历的代码示例:
深度优先遍历:
```c
#include <stdio.h>
#define MAX 100
int visited[MAX]; // 记录节点是否被访问过
int graph[MAX][MAX]; // 存储图的邻接矩阵
int n; // 图中节点的个数
void dfs(int v) {
visited[v] = 1; // 标记节点v已被访问
printf("%d ", v); // 输出节点v
for (int i = 0; i < n; i++) {
if (graph[v][i] == 1 && visited[i] == 0) { // 如果节点v和节点i之间有边,并且节点i未被访问
dfs(i); // 递归访问节点i
}
}
}
int main() {
// 读入图的邻接矩阵和节点个数
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
// 从节点0开始深度优先遍历
dfs(0);
return 0;
}
```
广度优先遍历:
```c
#include <stdio.h>
#define MAX 100
int visited[MAX]; // 记录节点是否被访问过
int graph[MAX][MAX]; // 存储图的邻接矩阵
int n; // 图中节点的个数
void bfs(int v) {
int queue[MAX]; // 定义队列
int front = 0, rear = 0; // 定义队列的头和尾
visited[v] = 1; // 标记节点v已被访问
printf("%d ", v); // 输出节点v
queue[rear++] = v; // 将节点v入队
while (front != rear) { // 队列不为空时循环
int w = queue[front++]; // 取出队头元素w
for (int i = 0; i < n; i++) {
if (graph[w][i] == 1 && visited[i] == 0) { // 如果节点w和节点i之间有边,并且节点i未被访问
visited[i] = 1; // 标记节点i已被访问
printf("%d ", i); // 输出节点i
queue[rear++] = i; // 将节点i入队
}
}
}
}
int main() {
// 读入图的邻接矩阵和节点个数
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
// 从节点0开始广度优先遍历
bfs(0);
return 0;
}
```
阅读全文