欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

邻接矩阵无向图的广度优先遍历C/C++代码实现

程序员文章站 2022-06-13 11:37:57
...

广度优先遍历:

与深度优先遍历不同,广度优先遍历还需要一个辅助队列,用来按顺序存储遍历过的顶点以便出队的顶点总是先被遍历的顶点。

以该图为例:
邻接矩阵无向图的广度优先遍历C/C++代码实现

代码如下:

#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);
}

运行结果:

邻接矩阵无向图的广度优先遍历C/C++代码实现