设计一程序,建立图的邻接矩阵,并且进行图的广度优先遍历。 用c语言
时间: 2024-02-29 15:51:59 浏览: 12
好的,下面是一个简单的程序,用于创建图的邻接矩阵并进行广度优先遍历。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接矩阵的定义
typedef struct {
int edges[MAX_VERTICES][MAX_VERTICES];
int n;
} Graph;
// 创建图的邻接矩阵
void createGraph(Graph* g) {
int i, j, k, x;
printf("请输入图中顶点的个数:");
scanf("%d", &(g->n));
for (i = 0; i < g->n; i++) {
for (j = 0; j < g->n; j++) {
g->edges[i][j] = 0;
}
}
for (i = 0; i < g->n; i++) {
printf("请输入顶点 %d 的出边(-1 结束):", i);
scanf("%d", &x);
while (x != -1) {
g->edges[i][x] = 1;
scanf("%d", &x);
}
}
}
// 广度优先遍历
void bfs(Graph* g, int v, int* visited) {
int queue[MAX_VERTICES], front = 0, rear = 0;
int i, j;
visited[v] = 1;
printf("%d ", v);
queue[rear++] = v;
while (front != rear) {
i = queue[front++];
for (j = 0; j < g->n; j++) {
if (g->edges[i][j] && !visited[j]) {
visited[j] = 1;
printf("%d ", j);
queue[rear++] = j;
}
}
}
}
int main() {
Graph g;
int visited[MAX_VERTICES];
int i;
createGraph(&g);
for (i = 0; i < g.n; i++) {
visited[i] = 0;
}
printf("从顶点 0 开始的广度优先遍历:");
bfs(&g, 0, visited);
printf("\n");
return 0;
}
```
这个程序中,我们首先定义了一个 `Graph` 结构体,用于保存图的邻接矩阵。 `createGraph` 函数用于读入图的边信息并建立邻接矩阵。 `bfs` 函数用于进行广度优先遍历。在 `main` 函数中,我们调用 `createGraph` 函数建立邻接矩阵,然后调用 `bfs` 函数进行广度优先遍历。