图的带权邻接表广度优先遍历c语言
时间: 2023-09-28 14:10:12 浏览: 51
以下是使用带权邻接表实现图的广度优先遍历的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100 // 最大顶点数
typedef int Vertex; // 顶点类型为整型
typedef int WeightType; // 权重类型为整型
// 边结构体
typedef struct ENode {
Vertex v1, v2; // 有向边<v1, v2>
WeightType weight; // 权重
}ENode;
// 邻接点结构体
typedef struct AdjVNode {
Vertex adjv; // 邻接点下标
WeightType weight; // 权重
struct AdjVNode* next; // 指向下一个邻接点的指针
}AdjVNode;
// 顶点结构体
typedef struct Vnode {
AdjVNode* firstedge; // 指向第一个邻接点的指针
}Vnode, AdjList[MaxVertexNum];
// 图结构体
typedef struct GNode {
int Nv; // 顶点数
int Ne; // 边数
AdjList G; // 邻接表
}GNode, *PtrToGNode;
typedef PtrToGNode Graph;
int visited[MaxVertexNum]; // 访问标记数组
// 创建图并初始化
Graph CreateGraph(int VertexNum)
{
Vertex v;
Graph G = (Graph)malloc(sizeof(GNode));
G->Nv = VertexNum;
G->Ne = 0;
for (v = 0; v < G->Nv; v++)
G->G[v].firstedge = NULL;
return G;
}
// 插入边
void InsertEdge(Graph G, ENode* e)
{
AdjVNode* newnode;
// 为v1插入边<v1, v2>
newnode = (AdjVNode*)malloc(sizeof(AdjVNode));
newnode->adjv = e->v2;
newnode->weight = e->weight;
newnode->next = G->G[e->v1].firstedge;
G->G[e->v1].firstedge = newnode;
// 为v2插入边<v2, v1>(无向图)
newnode = (AdjVNode*)malloc(sizeof(AdjVNode));
newnode->adjv = e->v1;
newnode->weight = e->weight;
newnode->next = G->G[e->v2].firstedge;
G->G[e->v2].firstedge = newnode;
}
// 构造图
Graph BuildGraph()
{
Graph G;
ENode* e;
Vertex v;
int Nv, i;
printf("请输入顶点数: ");
scanf("%d", &Nv);
G = CreateGraph(Nv);
printf("请输入边数: ");
scanf("%d", &(G->Ne));
if (G->Ne != 0) {
e = (ENode*)malloc(sizeof(ENode));
printf("请输入每条边的起点、终点和权重: ");
for (i = 0; i < G->Ne; i++) {
scanf("%d %d %d", &e->v1, &e->v2, &e->weight);
InsertEdge(G, e);
}
}
// 如果顶点有数据的话,读入数据
for (v = 0; v < G->Nv; v++)
scanf("%d", &(G->G[v].data));
return G;
}
// 遍历顶点v所在的连通块
void BFS(Graph G, Vertex v)
{
AdjVNode* W;
Queue Q = CreateQueue(); // 创建空队列
printf("访问顶点 %d\n", v);
visited[v] = 1; // 标记为已访问
Enqueue(Q, v); // 将v入队列
while (!IsEmpty(Q)) { // 只要队列不空
v = Dequeue(Q); // 将队首顶点出队列
for (W = G->G[v].firstedge; W; W = W->next) { // 对v的每个邻接点W->adjv
if (!visited[W->adjv]) { // 若W未被访问
printf("访问顶点 %d\n", W->adjv);
visited[W->adjv] = 1; // 标记为已访问
Enqueue(Q, W->adjv); // 将W入队列
}
}
}
}
// 遍历图
void BFSTraverse(Graph G)
{
Vertex v;
for (v = 0; v < G->Nv; v++)
visited[v] = 0; // 初始化访问标记数组
for (v = 0; v < G->Nv; v++) {
if (!visited[v]) // 若顶点v未被访问
BFS(G, v); // 访问顶点v所在的连通块
}
}
```
其中,`ENode`表示边结构体,包含两个顶点和权重;`AdjVNode`表示邻接点结构体,包含邻接点下标、权重和指向下一个邻接点的指针;`Vnode`表示顶点结构体,包含指向第一个邻接点的指针;`AdjList`表示邻接表,是一个大小为`MaxVertexNum`的`Vnode`数组;`GNode`表示图结构体,包含顶点数、边数和邻接表。`CreateGraph`函数创建图并初始化,`InsertEdge`函数插入边,`BuildGraph`函数构造图,`BFS`函数遍历顶点v所在的连通块,`BFSTraverse`函数遍历图。