有趣的数据结构算法19——图的广度优先搜索（BFS）算法实现

r囧r小猫 2024-04-17 05:42 60阅读 0赞

### 有趣的数据结构算法19——图的广度优先搜索（BFS）算法实现 ###

*  图的基本概念
 *   *  1、有向图和无向图
     *  2、权值与网
     *  3、顶点的度
     *  4、邻接矩阵表示法
 *  BFS的实现方法
 *  利用c语言实现BFS
 *  GITHUB下载连接

最近学习了新的数据结构，图，想到树也可以遍历，我就知道，最开始的图，也是需要遍历的！  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 图的基本概念 #

从各种数据结构上来看，线性表内包含的是1对1的关系，树包含的是1对多的关系，而图包含的是多对多的关系，一个图可以表示一个社交网络，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。这是一个随意的图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]

## 1、有向图和无向图 ##

有向图与无向图的区别是，对于无向图而言，在一条边(u，v)中，u和v不存在谁指向谁的方向关系，即（u，v）和（v，u）是同一条边。无向图的边常用一对圆括号表示。  
如下便是一张无向图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]  
对于有向图而言，在一条边<u，v>中，u和v存在谁指向谁的方向关系，即<u，v>和<v，u>不是同一条边，<u，v>代表u指向v，<v，u>代表v指向u。有向图的边常用一对尖括号表示。  
如下是一个有向图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 1]

## 2、权值与网 ##

图的结构常常会让我们想起地图，在地图上两个点之间是存在距离的，在图中我们可以把这种“距离”类似的概念称为，即图的每条边上可能存在具有某种含义的数值，称该数值为该边上的权。  
就像这样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 2]  
这种存在权值的图被称作网。

## 3、顶点的度 ##

顶点的度：顶点关联的边的数目。  
无向图中顶点的度就是顶点周围边的数量。  
有向图中存在入度和出度，入读指的是方向指向顶点的边；出度指的是方向背向顶点的边。在有向图中顶点的度就是两者之和。

## 4、邻接矩阵表示法 ##

在邻接矩阵中，用两个数组保存数据。一个一维数组存储图中的顶点信息，一个二维数组存储图中的边或弧的信息。  
对于这样一幅无向图而言：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 3]  
其邻接矩阵表示法的顶点数组和边数组分别为：  
![在这里插入图片描述][20190823153258837.png_pic_center]  
对于这样一副有向图而言：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 4]  
其邻接矩阵表示法的顶点数组和边数组分别为：  
![在这里插入图片描述][20190823153644951.png_pic_center]

# BFS的实现方法 #

广度优先搜索与树的层次遍历过程类似。  
常常需要借助一个队列来实现图的广度优先搜索。  
以下图为例，要想遍历abcdef六个顶点，可以将整幅图设为三层，a为第一层，b、c、d为第二层，e、f为第三层，再逐个遍历每一层的每个顶点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]  
具体遍历的过程如下：  
1、创建一个visited数组，用来记录已被访问过的点；创建一个队列，用来存放按照遍历顺序存放的点；初始化图Graph。  
2、从图中的a开始访问，将的visited\[0\]数组的值设置为1，同时将v0入队。  
3、while队列不空： a、队头head出队，显示内容； b、检查head所有的邻接点n，若visited\[n\]的值为0，则代表该点尚未被访问过；c、访问n，并将visited\[n\]置为1，同时将n压入队列。  
假设顶点数组的存储顺序为：a、b、c、d、e、f。  
那么遍历结果为：  
a b c d e f。  
接下来我将具体展示如何进行BFS：  
**白底代表尚未访问，黄底代表已经访问！**  
1、初始状态。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 5]  
2、访问a点，根据顶点数组的存储顺序，visited\[0\]设为1；将a压入队列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 6]  
3、将a点取出队列，访问其周围所有邻接点，若对应visited\[n\]的值为0，则代表该点尚未被访问过，访问之，并将其压入队列，访问顺序根据顶点数组的存储顺序决定，存储顺序为a b c d e f。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 9]  
4、所有邻接点访问完后，重新取出队头元素，此时队头元素为b，访问其周围所有邻接点，若对应visited\[n\]的值为0，则代表该点尚未被访问过，访问之，并将其压入队列，访问顺序根据顶点数组的存储顺序决定，存储顺序为a b c d e f。在本步骤中，由于d已经被访问，因此无需再次访问，紧接着访问e f。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]  
此时便完成了所有点的访问。在接下来的时间里，c d e f会依次出队，由于visted数组全为1，访问结束。

# 利用c语言实现BFS #

#include<stdlib.h>
    #include<stdio.h>
    
    #define VexNum 100
    
    typedef char Ele;
    
    struct Node{
        
    	Ele data;
    	struct Node* Next;		//data用于存储信息，Next用于存储下一个队列下一个元素的地址。
    };
    
    typedef struct Node* LinkedList;
    
    struct Queue{
        
    	LinkedList head;
    	LinkedList tail;		//head为队头，tail为队尾。
    };
    
    typedef struct Queue QueueList;
    
    void init(QueueList* q){
        
    	q->head = q->tail = (LinkedList)malloc(sizeof(struct Node));
    	if (q->head == NULL){
        
    		printf("内存空间分配失败");
    		exit(1);
    	}
    	q->head->Next = NULL;
    }
    
    void push(QueueList* q, Ele e){
        
    	LinkedList p;
    	p = (LinkedList)malloc(sizeof(struct Node));
    	if (p == NULL){
        
    		printf("内存空间分配失败");
    		exit(1);
    	}
    	p->Next = NULL;
    	p->data = e;
    
    	q->tail->Next = p;	//将元素压入队列、将队尾指针指向新节点
    	q->tail = p;
    }
    
    void pop(QueueList* q,Ele *e){
        
    	LinkedList p;
    	if (q->head == q->tail){
        
    		printf("队列已空");
    		exit(1);
    	}
    	p = q->head->Next;
    	q->head->Next = p->Next;	//利用p取出队头
    	*e = p->data;
    	if (q->tail == p){
        
    		q->tail = q->head;		//判断是否取出所有元素，如果取出所有元素，队头指向队尾
    	}
    	free(p);					//释放中间节点
    }
    
    bool empty(QueueList* q){
        
    	return q->head == q->tail;
    }
    
    typedef struct Graph			//利用邻接矩阵表示
    {
        						
    	char vexs[VexNum];			//顶点
    	int arcs[VexNum][VexNum];	//边	
    	int vexnum, arcnum;			//顶点和边的数量
    }Graph;
    
    int LocateVex(Graph *G, char c)	//输入顶点符号，寻找其对应的位置
    {
        
    	for (int i = 0; i < G->vexnum; i++)
    	{
        
    		if (G->vexs[i] == c)
    			return i;
    	}
    }
    
    void initGraph(Graph *G)					//图的初始化
    {
        
    	int i, j;
    	char c1, c2;
    
    	scanf("%d %d", &G->vexnum, &G->arcnum);
    	getchar();
    
    	for (i = 0; i < G->vexnum; i++)
    		for (j = 0; j < G->vexnum; j++)
    			G->arcs[i][j] = 0;				//初始化每条边为0
    
    	for (i = 0; i < G->vexnum; i++)
    		scanf("%c", &G->vexs[i]);			//输入点的信息
    
    	for (int k = 0; k < G->arcnum; k++)			//创建边的信息
    	{
        
    		getchar();
    		scanf("%c%c", &c1, &c2);			//输入一条边依附的顶点
    		i = LocateVex(G, c1);				//找到顶点i的下标
    		j = LocateVex(G, c2);				//找到顶点j的下标
    
    		G->arcs[i][j] = G->arcs[j][i] = 1;
    	}
    }
    
    bool visited[VexNum];
    
    void BFS(Graph *G, char c0)					//从c0开始遍历整个图
    {
        
    	QueueList q;
    	char e;
    	int index0,i;
    
    	init(&q);
    	for (i = 0; i < G->vexnum; i++){
        
    		visited[i] = 0;
    	}
    
    	index0 = LocateVex(G, c0);
    
    	visited[index0] = 1;
    	push(&q,c0);
    	printf("%c ", c0);
    
    	while (!empty(&q))
    	{
        
    		pop(&q,&e);
    		index0 = LocateVex(G, e);
    						
    		for (i = 0; i < G->vexnum; i++)
    		{
        
    			
    			if (G->arcs[index0][i] && !visited[i])
    			{
        
    				e = G->vexs[i];
    				printf("%c ", e);	//打印顶点w
    				push(&q,e);		//将顶点w入队
    				visited[i] = 1;		//顶点w已被访问
    			}
    		}
    	}
    }
    
    void main(){
        
    	Graph G;
    	initGraph(&G);
    	BFS(&G,'a');
    }

输出结果为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 11]

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723170158884.jpg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/1d4d0b0960fc4102a2f5cb4e388a690c.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/93dbc6e6e76645fe9d72efe1b5b92637.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/195a0cf6259f45a38312d6d21663f296.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/2687d29fe3284cd7bc594913785514d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/6d58c1f70d8245e79d02787f43470ec3.png
[20190823153258837.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/7c555ed6a7c3456c869676506cd3a224.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/e4644e560633405b8e25cee4bc8fd823.png
[20190823153644951.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f24f4f9df4b14701996772b1a240e91f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/c439ed843ba44f7f85b5ba27ff9bd51e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/b99d45aacdaf4f1a8a99a0901feb2f25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/30ebf99f529b42768b867532a7fdecee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/e534d066fd824aa49637a09357af0088.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/ea9b5e466fc047168dfee31f222603a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/1570f98184724da3bb82c30cfb2e1e2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/061a87193975421a8ae36de31c459d4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 11]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/93da6dfc22bc4fb598a1781bafbd5a9e.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm