用c英语实现, 建立一个有向图的邻接表存储,并且逐个链表输出,然后从0号顶 点出发对该图进行广度优先搜索,按顺序输出所访问的顶点
时间: 2024-02-15 07:01:50 浏览: 66
无向图的邻接表存储及输出
4星 · 用户满意度95%
好的,我了解了您的问题。以下是用C语言实现建立有向图的邻接表存储,并且逐个链表输出,然后从0号顶点出发对该图进行广度优先搜索,按顺序输出所访问的顶点的代码:
```c
#include <stdio.h>
#include <stdlib.h>
//定义邻接表中的边结构体
typedef struct EdgeNode {
int adjvex; //邻接点的下标
struct EdgeNode* next; //指向下一个邻接点的指针
}EdgeNode;
//定义邻接表中的顶点结构体
typedef struct VertexNode {
int data; //顶点的数据
EdgeNode* firstedge; //指向第一个邻接点的指针
}VertexNode;
//定义图结构体
typedef struct Graph {
VertexNode vexs[100]; //存储顶点的数组
int vexnum, edgenum; //顶点数和边数
}Graph;
//初始化图
void initGraph(Graph* G) {
int i;
//初始化每个顶点的第一个邻接点指针为NULL
for (i = 0; i < G->vexnum; i++) {
G->vexs[i].firstedge = NULL;
}
}
//创建图
void createGraph(Graph* G) {
int i, j, k, w;
EdgeNode* e;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->edgenum);
printf("请输入顶点的数据:");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vexs[i].data);
}
//输入边的信息,构建邻接表
for (k = 0; k < G->edgenum; k++) {
printf("请输入第%d条边的起始顶点、结束顶点和权值:", k + 1);
scanf("%d%d%d", &i, &j, &w);
//创建一个新的邻接点
e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = j;
//将新邻接点插入到顶点i的邻接表中
e->next = G->vexs[i].firstedge;
G->vexs[i].firstedge = e;
}
}
//输出图的邻接表
void printGraph(Graph* G) {
int i;
EdgeNode* p;
for (i = 0; i < G->vexnum; i++) {
printf("顶点%d的邻接表:", i);
p = G->vexs[i].firstedge;
while (p != NULL) {
printf("->%d", p->adjvex);
p = p->next;
}
printf("\n");
}
}
//广度优先搜索
void BFS(Graph* G, int start) {
int visited[100] = { 0 }; //初始化所有顶点为未访问状态
int queue[100], front = 0, rear = 0; //定义队列
int i, j;
EdgeNode* p;
visited[start] = 1; //标记起始顶点为已访问
queue[rear++] = start; //起始顶点入队
printf("广度优先搜索结果:");
while (front < rear) {
j = queue[front++]; //取出队首元素
printf("%d ", G->vexs[j].data); //输出访问的顶点
p = G->vexs[j].firstedge;
while (p != NULL) {
i = p->adjvex;
if (visited[i] == 0) { //如果邻接点未被访问,则标记为已访问并入队
visited[i] = 1;
queue[rear++] = i;
}
p = p->next;
}
}
printf("\n");
}
int main() {
Graph G;
createGraph(&G);
initGraph(&G);
printGraph(&G);
BFS(&G, 0);
return 0;
}
```
以上代码中,我们首先定义了邻接表中的边结构体和顶点结构体,以及图结构体。然后我们通过initGraph函数初始化每个顶点的第一个邻接点指针为NULL。接着我们通过createGraph函数输入图的信息,构建邻接表。然后我们通过printGraph函数逐个链表输出邻接表。最后我们通过BFS函数从0号顶点出发对该图进行广度优先搜索,按顺序输出所访问的顶点。
阅读全文