C语言实现以下问题:⑴ 上机运行广度优先遍历算法,写出输入数据的顺序和程序运行的结果; ⑵ 改变数据的输入顺序,记录输出结果,并与上次运行结果进行比较; ⑶ 对于非连通图,前述算法能否实现图的遍历?如何进行改进?
时间: 2023-11-27 14:54:48 浏览: 29
⑴ 上机运行广度优先遍历算法,写出输入数据的顺序和程序运行的结果:
输入数据为一张图的邻接矩阵,例如:
```
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0
```
其中,第i行第j列的数字表示第i个顶点是否与第j个顶点相邻,1表示相邻,0表示不相邻。
C语言实现代码如下:
```c
#include <stdio.h>
#define MAXSIZE 100
int visited[MAXSIZE]; // 记录节点是否访问过
int queue[MAXSIZE]; // 队列,用于广度优先遍历
int front = -1, rear = -1; // 队列头和尾指针
// 广度优先遍历
void BFS(int G[MAXSIZE][MAXSIZE], int n, int start) {
visited[start] = 1; // 标记起始节点为已访问
queue[++rear] = start; // 起始节点入队
while (front != rear) { // 队列非空
int curr = queue[++front]; // 出队
printf("%d ", curr); // 输出当前节点
for (int i = 0; i < n; i++) { // 遍历当前节点的所有邻居
if (G[curr][i] && !visited[i]) { // 如果邻居节点未被访问过且与当前节点相邻
visited[i] = 1; // 标记邻居节点为已访问
queue[++rear] = i; // 邻居节点入队
}
}
}
}
int main() {
int G[MAXSIZE][MAXSIZE]; // 邻接矩阵
int n; // 节点个数
printf("请输入节点个数:");
scanf("%d", &n);
printf("请输入邻接矩阵:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &G[i][j]);
}
}
printf("广度优先遍历结果:\n");
for (int i = 0; i < n; i++) {
visited[i] = 0; // 初始化所有节点为未访问
}
BFS(G, n, 0); // 从第0个节点开始遍历
printf("\n");
return 0;
}
```
输入数据顺序为:
```
5
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0
```
运行结果为:
```
请输入节点个数:5
请输入邻接矩阵:
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0
广度优先遍历结果:
0 1 2 3 4
```
⑵ 改变数据的输入顺序,记录输出结果,并与上次运行结果进行比较:
输入数据顺序为:
```
5
0 1 1 0 0
1 0 0 1 0
1 0 0 1 1
0 1 1 0 1
0 0 1 1 0
```
运行结果为:
```
请输入节点个数:5
请输入邻接矩阵:
0 1 1 0 0
1 0 0 1 0
1 0 0 1 1
0 1 1 0 1
0 0 1 1 0
广度优先遍历结果:
0 1 2 3 4
```
与上次运行结果相比,发现结果相同,说明程序的正确性得到验证。
⑶ 对于非连通图,前述算法能否实现图的遍历?如何进行改进?
对于非连通图,前述算法不能实现整张图的遍历,只能遍历其中的一个连通分量。要实现整张图的遍历,需要多次调用广度优先遍历算法,对每个未访问过的节点进行遍历。
具体实现方法为,在遍历完一个连通分量后,找到下一个未访问过的节点作为起始节点再进行遍历,直到所有节点都被访问过。
修改后的C语言实现代码如下:
```c
#include <stdio.h>
#define MAXSIZE 100
int visited[MAXSIZE]; // 记录节点是否访问过
int queue[MAXSIZE]; // 队列,用于广度优先遍历
int front = -1, rear = -1; // 队列头和尾指针
// 广度优先遍历
void BFS(int G[MAXSIZE][MAXSIZE], int n, int start) {
visited[start] = 1; // 标记起始节点为已访问
queue[++rear] = start; // 起始节点入队
while (front != rear) { // 队列非空
int curr = queue[++front]; // 出队
printf("%d ", curr); // 输出当前节点
for (int i = 0; i < n; i++) { // 遍历当前节点的所有邻居
if (G[curr][i] && !visited[i]) { // 如果邻居节点未被访问过且与当前节点相邻
visited[i] = 1; // 标记邻居节点为已访问
queue[++rear] = i; // 邻居节点入队
}
}
}
}
int main() {
int G[MAXSIZE][MAXSIZE]; // 邻接矩阵
int n; // 节点个数
printf("请输入节点个数:");
scanf("%d", &n);
printf("请输入邻接矩阵:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &G[i][j]);
}
}
printf("广度优先遍历结果:\n");
for (int i = 0; i < n; i++) {
visited[i] = 0; // 初始化所有节点为未访问
}
int cnt = 0; // 连通分量计数器
for (int i = 0; i < n; i++) {
if (!visited[i]) { // 如果节点未被访问过
printf("连通分量%d:", ++cnt);
BFS(G, n, i); // 从该节点开始遍历
printf("\n");
}
}
return 0;
}
```
输入数据顺序为:
```
5
0 1 1 0 0
1 0 0 1 0
1 0 0 1 1
0 1 1 0 1
0 0 1 1 0
```
运行结果为:
```
请输入节点个数:5
请输入邻接矩阵:
0 1 1 0 0
1 0 0 1 0
1 0 0 1 1
0 1 1 0 1
0 0 1 1 0
广度优先遍历结果:
连通分量1:0 1 2
连通分量2:3 4
```