邻接矩阵无向图的广度优先遍历C/C++代码实现
程序员文章站
2022-06-13 11:37:57
...
广度优先遍历:
与深度优先遍历不同,广度优先遍历还需要一个辅助队列,用来按顺序存储遍历过的顶点以便出队的顶点总是先被遍历的顶点。
以该图为例:
代码如下:
#include<stdio.h>
#define MaxInt 0
#define MVNum 100
typedef char VerTexType; //顶点类型
typedef int ArcType; //边权值类型
//邻接矩阵存储结构
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的当前点数和边数
}AMGraph;
void printGraph(AMGraph G);
int LocateVex(AMGraph G, char v);
//创建无向网
void CreateUDN(AMGraph &G)
{
G.vexnum = 8; //输入总顶点数和边数
G.arcnum = 9;
G.vexs[0] = 'v1'; //输入顶点信息
G.vexs[1] = 'v2';
G.vexs[2] = 'v3';
G.vexs[3] = 'v4';
G.vexs[4] = 'v5';
G.vexs[5] = 'v6';
G.vexs[6] = 'v7';
G.vexs[7] = 'v8';
for (int i = 0; i < G.vexnum; i++) //初始化邻接矩阵为极大值
{
for (int j = 0; j < G.vexnum; j++)
{
G.arcs[i][j] = MaxInt;
}
}
//建立边
int i, j;
i = LocateVex(G, 'v1');
j = LocateVex(G, 'v2');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v1');
j = LocateVex(G, 'v3');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v2');
j = LocateVex(G, 'v4');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v2');
j = LocateVex(G, 'v5');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v5');
j = LocateVex(G, 'v8');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v4');
j = LocateVex(G, 'v8');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v3');
j = LocateVex(G, 'v6');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v3');
j = LocateVex(G, 'v7');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v6');
j = LocateVex(G, 'v7');
G.arcs[i][j] = G.arcs[j][i] = 1;
printGraph(G);
}
//确定顶点在顶点表数组中的下边,并返回
int LocateVex(AMGraph G, char v)
{
for (int i = 0; i < G.vexnum; i++)
{
if (G.vexs[i] == v)
{
return i;
}
}
}
//输出打印
void printGraph(AMGraph G)
{
for (int i = 0; i < G.vexnum; i++)
{
printf("v%d :", i + 1);
for (int j = 0; j < G.vexnum; j++)
{
printf("%d ", G.arcs[i][j]);
}
printf("\n");
}
}
//邻接矩阵广度优先遍历
//创建队列
typedef struct
{
int base[MVNum];
int front;
int rear;
}SqQueue;
//初始化
int InitQueue(SqQueue &Q)
{
Q.front = Q.rear = 0;
return 1;
}
//入队
int EnQueue(SqQueue &Q, int e)
{
if ((Q.rear + 1) % MVNum == Q.front) return 0;
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MVNum;
}
//出队
int DeQueue(SqQueue &Q, int &e)
{
if (Q.front == Q.rear) return 0;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MVNum;
return 1;
}
bool visited[MVNum]; //辅助数组
void BFS_AM(AMGraph G, int v)
{
int u;
printf("v%c->", G.vexs[v]);
visited[v] = true;
SqQueue Q;
InitQueue(Q);
EnQueue(Q, v);
while (Q.front != Q.rear)
{
DeQueue(Q, u); //出队列并放入u中
for (int j = 0; j < G.vexnum; j++)
{
if (G.arcs[u][j] == 1 && !visited[j]) //查询与u有边的顶点时候被访问
{
printf("v%c->", G.vexs[j]);
visited[j] = true;
EnQueue(Q, j);
}
}
}
}
int main()
{
AMGraph G;
CreateUDN(G);
int v = 0;
BFS_AM(G, v);
}
运行结果:
上一篇: 图:图的邻接矩阵创建、深度优先遍历和广度优先遍历详解
下一篇: OpenFeign服务接口调用