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

拼搏现实的明天。 2023-02-17 14:26 18阅读 0赞

## 广度优先遍历： ##

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

以该图为例：  
![在这里插入图片描述][20200614142756974.png]

## 代码如下： ##

#include<stdio.h>
    
    #define MVNum 100
    typedef char OtherInfo;
    typedef char VerTexType;
    
    //邻接表存储结构 
    typedef struct ArcNode			//边结点
    {
        
    	int adjvex;
    	struct ArcNode *nextarc;
    	OtherInfo info;
    }ArcNode;
    typedef struct VNode			//顶点信息
    {
        
    	VerTexType data;
    	ArcNode *firstarc;
    }VNode, AdjList[MVNum];
    typedef struct                  //邻接表
    {
        
    	AdjList vertices;
    	int vexnum, arcnum;
    }ALGraph;
    int LocateVex(ALGraph G, char v);
    void LinkAL(ALGraph &G, int i, int j);
    
    
    
    //邻接表创建无向图
    void CreateUDG(ALGraph &G)
    {
        
    	G.vexnum = 8;						//输入总顶点数和边数
    	G.arcnum = 9;
    	G.vertices[0].data = 'v1';			//输入顶点信息
    	G.vertices[0].firstarc = NULL;
    	G.vertices[1].data = 'v2';
    	G.vertices[1].firstarc = NULL;
    	G.vertices[2].data = 'v3';
    	G.vertices[2].firstarc = NULL;
    	G.vertices[3].data = 'v4';
    	G.vertices[3].firstarc = NULL;
    	G.vertices[4].data = 'v5';
    	G.vertices[4].firstarc = NULL;
    	G.vertices[5].data = 'v6';
    	G.vertices[5].firstarc = NULL;
    	G.vertices[6].data = 'v7';
    	G.vertices[6].firstarc = NULL;
    	G.vertices[7].data = 'v8';
    	G.vertices[7].firstarc = NULL;
    
    	int i, j;							//输入边信息
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v2');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v4');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v5');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v5');
    	j = LocateVex(G, 'v8');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v8');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v3');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v6');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v7');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v6');
    	j = LocateVex(G, 'v7');
    	LinkAL(G, i, j);
    }
    
    //连接边结点
    void LinkAL(ALGraph &G, int i, int j)
    {
        
    	ArcNode *p1;
    	p1 = new ArcNode;
    	p1->adjvex = j;
    	p1->nextarc = G.vertices[i].firstarc;						  //头插法
    	G.vertices[i].firstarc = p1;
    
    	ArcNode *p2;
    	p2 = new ArcNode;
    	p2->adjvex = i;
    	p2->nextarc = G.vertices[j].firstarc;
    	G.vertices[j].firstarc = p2;
    }
    
    //确定顶点在顶点表数组中的下边，并返回
    int LocateVex(ALGraph G, char v)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (G.vertices[i].data == v)
    		{
        
    			return i;
    		}
    	}
    }
    
    //输出打印
    void printGraph(ALGraph G)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		printf("%d :", i);
    		printf("v%d ->", i + 1);
    
    		ArcNode *p;
    		p = G.vertices[i].firstarc;
    		while (p != NULL)
    		{
        
    			printf("%d->", p->adjvex);
    			p = p->nextarc;
    		}
    		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_AL(ALGraph G, int v)
    {
        
    	printf("v%c->", G.vertices[v].data);
    	visited[v] = true;
    
    	SqQueue Q;
    	InitQueue(Q);
    	EnQueue(Q, v);
    
    	ArcNode *w;
    	while (Q.front != Q.rear)
    	{
        
    		int u = 0;
    		DeQueue(Q, u);
    		w = G.vertices[u].firstarc;
    		while (w != NULL)
    		{
        
    			if (!visited[w->adjvex])
    			{
        
    				printf("v%c->", G.vertices[w->adjvex].data);
    				visited[w->adjvex] = true;
    				EnQueue(Q, w->adjvex);
    			}
    			w = w->nextarc;
    		}
    
    	}
    }
    
    int main()
    {
        
    	ALGraph G;
    	CreateUDG(G);
    	printGraph(G);
    
    	int v = 0;
    	BFS_AL(G, v);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[20200614142756974.png]: https://img-blog.csdnimg.cn/20200614142756974.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200614144016812.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70