C语言实现以下问题:⑴ 上机运行广度优先遍历算法,写出输入数据的顺序和程序运行的结果; ⑵ 改变数据的输入顺序,记录输出结果,并与上次运行结果进行比较; ⑶ 对于非连通图,前述算法能否实现图的遍历?如何进行改进?
时间: 2023-07-16 07:14:19 浏览: 25
⑴ 以下是广度优先遍历算法的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存储顶点信息
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边信息
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
typedef struct {
int data[MAX_VERTEX_NUM];
int front, rear;
} Queue;
void init_graph(Graph *graph) {
int i, j;
printf("请输入顶点数和边数:");
scanf("%d %d", &graph->vertex_num, &graph->edge_num);
getchar(); // 吃掉输入缓冲区中的换行符
printf("请输入顶点信息:");
for (i = 0; i < graph->vertex_num; i++) {
scanf("%d", &graph->vertex[i]);
}
getchar(); // 吃掉输入缓冲区中的换行符
for (i = 0; i < graph->vertex_num; i++) {
for (j = 0; j < graph->vertex_num; j++) {
graph->edge[i][j] = 0; // 初始化边信息
}
}
printf("请输入边信息(格式:i j):\n");
for (i = 0; i < graph->edge_num; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
graph->edge[v1][v2] = 1;
graph->edge[v2][v1] = 1; // 无向图的边是双向的
}
}
void init_queue(Queue *queue) {
queue->front = queue->rear = 0;
}
int is_queue_empty(Queue *queue) {
return queue->front == queue->rear;
}
void enqueue(Queue *queue, int data) {
queue->data[queue->rear++] = data;
}
int dequeue(Queue *queue) {
return queue->data[queue->front++];
}
void bfs(Graph *graph, int start_vertex) {
Queue queue;
int visited[MAX_VERTEX_NUM] = {0}; // 记录每个顶点是否被访问过
int i;
init_queue(&queue);
visited[start_vertex] = 1;
printf("%d ", graph->vertex[start_vertex]);
enqueue(&queue, start_vertex);
while (!is_queue_empty(&queue)) {
int v = dequeue(&queue);
for (i = 0; i < graph->vertex_num; i++) {
if (graph->edge[v][i] && !visited[i]) {
visited[i] = 1;
printf("%d ", graph->vertex[i]);
enqueue(&queue, i);
}
}
}
}
int main() {
Graph graph;
init_graph(&graph);
printf("请输入起始顶点编号:");
int start_vertex;
scanf("%d", &start_vertex);
bfs(&graph, start_vertex);
return 0;
}
```
假设我们输入以下数据:
```
请输入顶点数和边数:5 6
请输入顶点信息:0 1 2 3 4
请输入边信息(格式:i j):
0 1
0 2
1 3
2 3
2 4
3 4
请输入起始顶点编号:0
```
程序运行的结果为:
```
0 1 2 3 4
```
⑵ 如果我们改变输入数据的顺序,比如输入以下数据:
```
请输入顶点数和边数:5 6
请输入顶点信息:4 0 3 2 1
请输入边信息(格式:i j):
4 0
4 3
0 2
0 3
2 3
2 1
请输入起始顶点编号:4
```
程序运行的结果为:
```
4 0 3 2 1
```
可以看出,输出结果与上次运行结果不同,这是由于输入数据的不同导致的。
⑶ 对于非连通图,前述算法不能够遍历图中所有顶点。我们可以对算法进行改进,使其能够遍历非连通图。
一个简单的方法是从每个未访问过的顶点开始进行广度优先遍历,直到所有顶点都被访问过为止。具体实现可以在主函数中添加一个循环,每次找到一个未访问过的顶点作为起始顶点进行广度优先遍历,直到所有顶点都被访问过为止。代码如下:
```c
int main() {
Graph graph;
init_graph(&graph);
int visited[MAX_VERTEX_NUM] = {0};
int i;
for (i = 0; i < graph.vertex_num; i++) {
if (!visited[i]) {
bfs(&graph, i);
visited[i] = 1;
}
}
return 0;
}
```