用c语言写 广度遍历网 功能描述:推荐采用队列实现遍历网的功能,以用户指定的顶点为起点,输出顶点的广度优先访问序列 调用search(MGraph *MG, char V1)方法,找到遍历开始的顶点位置。 输出网的顶点信息printf("%c ", // 顶点信息); 参数说明:MG-MGraph型参数 返回值说明:无
时间: 2024-03-13 22:46:22 浏览: 22
以下是用 C 语言实现广度遍历网的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20
#define INFINITY 1000000
typedef struct {
char vexs[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum, arcnum;
} MGraph;
typedef struct {
int data[MAX_VERTEX_NUM];
int front, rear;
} Queue;
void initQueue(Queue *Q) {
Q->front = Q->rear = 0;
}
void enQueue(Queue *Q, int v) {
Q->data[Q->rear++] = v;
}
int deQueue(Queue *Q) {
return Q->data[Q->front++];
}
int isEmpty(Queue *Q) {
return Q->front == Q->rear;
}
void printVex(char vex) {
printf("%c ", vex);
}
void search(MGraph *MG, char V1, int *visited, Queue *Q) {
int i, j;
i = -1;
for (int m = 0; m < MG->vexnum; m++) {
if (MG->vexs[m] == V1) {
i = m;
break;
}
}
if (i == -1) {
return;
}
visited[i] = 1;
printVex(MG->vexs[i]);
enQueue(Q, i);
while (!isEmpty(Q)) {
i = deQueue(Q);
for (j = 0; j < MG->vexnum; j++) {
if (MG->arcs[i][j] != INFINITY && !visited[j]) {
visited[j] = 1;
printVex(MG->vexs[j]);
enQueue(Q, j);
}
}
}
}
void BFSTraverse(MGraph *MG, char V1) {
int visited[MAX_VERTEX_NUM];
memset(visited, 0, sizeof(visited));
Queue Q;
initQueue(&Q);
search(MG, V1, visited, &Q);
}
int main() {
MGraph G;
char V1;
createMGraph(&G);
printf("请输入遍历开始的顶点:\n");
scanf("%c", &V1);
BFSTraverse(&G, V1);
return 0;
}
```
在 `BFSTraverse()` 函数中,我们先创建一个 `visited` 数组,用来记录每个顶点是否已经被访问过。然后,我们通过调用 `search()` 函数来实现遍历网的功能。在 `search()` 函数中,我们首先找到遍历开始的顶点位置,并且将它的 `visited` 置为 1,表示已经被访问过。然后,我们输出该顶点的信息,将它入队。接着,我们不断出队,并且遍历它的邻接点,将未访问过的邻接点入队,并且将它们的 `visited` 置为 1。最终,我们就可以得到顶点的广度优先访问序列。
在实现时,我们采用了队列来实现遍历的功能。定义了 `Queue` 结构体,包含一个数组和两个指针,其中 `front` 指向队列头,`rear` 指向队列尾。我们通过 `enQueue()` 函数将元素入队,`deQueue()` 函数将元素出队,`isEmpty()` 函数判断队列是否为空。同时,我们也定义了一些常量,如 `MAX_VERTEX_NUM` 表示最大顶点数, `INFINITY` 表示无穷大(即两个顶点之间没有边)。最后,我们在主函数中调用 `BFSTraverse()` 函数来进行广度遍历。