【数据结构——图的遍历】

浅浅的花香味﹌ 2022-12-20 02:16 109阅读 0赞

### 【数据结构——图的遍历】 ###

*  一、介绍
 *  二、深度优先搜索DFS(Depth First Search)
 *   *   *  1、深度优先搜索遍历的过程
         *  2、深度优先搜索遍历的算法实现
         *  3、非连通图的深度优先搜索遍历
 *  三、广度优先搜索BFS(Breadth First Search)
 *   *   *  1、介绍
         *  2、算法思想和描述

# 一、介绍 #

**图的遍历：从图的某个顶点出发，依次访问图中所有的顶点，每个顶点被访问一次且仅访问一次。**  
**防止多次访问某一个顶点的思路：设置辅助数组visited\[n\],用来标记每个被访问的顶点，  
初始化状态为visited\[n\]=0;如果顶点被访问到，则修改辅助数组的值 ：visited\[i\]=1**

# 二、深度优先搜索DFS(Depth First Search) #

### 1、深度优先搜索遍历的过程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]  
**深度优先搜索生成树： 对于无向连通生成图，如果将第一次深度优先搜索时前进操作经过的边保留下来则可以构成一棵深度优先搜索生成树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

### 2、深度优先搜索遍历的算法实现 ###

**递归的搜索算法：dfs(G,v)**

/*图的深度优先搜索遍历伪码*/
    dfs(G, v)
    {
        
    	访问v，并对v作已访问标记
    	访问v的邻接点w,若w未被访问，则继续调用dfs(G,w)
    }

/*图的深度优先搜索遍历伪码*/
    bool visited[MVNum];//标志访问数组，初值为false
    void DFS(Graph G, int v)
    {
        //从第v个顶点开始深度优先搜索遍历图G
    	cout << v;visited[v] = true;//访问第一个顶点v ,访问标志符置为true
    	for (w = FirstAdjVex(G,v);w >= 0;w = NextAdjVex(G, v, w))
    	{
        
    		if (!visited[w])
    			DFS(G, w);//对v的没有被访问的顶点递归遍历
    	}
    }
    //FirstAdjVex(G,v)表示v的第一个邻接点
    //NextAdjVex(G, v, w)表示v相对于w的下一个邻接点

**采用邻接矩阵表示的图的DFS:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]

/*邻接矩阵的存储结构*/
    typedef struct
    {
        
    	VerTexType vexs[MVNum];//顶点表
    	ArcType arcs[MVNum][MVNum];//邻接矩阵
    	int vexnum, arcnum;//当前图的顶点数和边数
    }AMGraph;
    /*邻接矩阵表示的图的DFS*/
    void DFS_AM(AMGraph G, int v)
    {
        //从第v个顶点依次遍历图G
    	cout << v;//访问第v个顶点
    	visited[v] = true;//访问标志符数组置为true
    	for (w = 0;w <= G.vexnum;++w)//依次检查邻接矩阵v所在行
    	{
        
    		if ((G.arcs[v][w] != 0) && (!visited[w]))
    			DFS_AM(G, w);//w是v的邻接点，如果w未被访问，则调用DFS_AM
    	}
    }

*用邻接矩阵表示图：查找每个结点的邻接点的时间复杂度为O(n的平方），加上初始化visited数组时间复杂度O(n),DFS的时间复杂度为O(n的平方）*

**采用邻接表表示图的DFS**

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

/*图的邻接表的存储定义*/
    //弧的结点结构
    #define MVNum 100	//最大的顶点数
    typedef struct ArcNode
    {
        
    	int adjvex;	//该边所指的顶点的位置
    	struct ArcNode* nextarc;	//指向下一条边的指针
    	OtherInfo info;	//和边相关的信息
    }ArcNode;
    //顶点的结点结构
    typedef struct VNode
    {
        
    	VertexType data;//顶点信息
    	ArcNode* firstarc;//指向第一条依附该顶点的边
    }VNode, AdjList[MVNum];//AdjList表示邻接表类型
    //AdjList v相当于VNode v[MVNum]
    
    //图的结构定义（邻接表）
    typedef struct
    {
        
    	AdjList vertices;//vertices是vertex的复数
    	int vexnum, arcnum;//图的当前顶点数和边数
    }ALGraph;
    
    /*采用邻接表表示图的DFS*/
    void DFS_AL(ALGraph G, int v)
    {
        //图G为邻接表类型，从第v个结点出发DFS图G
    	cout << v;//访问第v个顶点
    	visited[v] = true;//置访问标志符为true
    	p = G.vertices[v].firstarc;//p指向v的边链表的第一个边结点
    	while (p != NULL)//边结点非空
    	{
        
    		w = p->adjvex;//w是p的邻接点下标
    		if (!visited[w])
    			DFS_AL(G, w);//如果w未访问，则递归调用DFS_AL
    		p = p->nextarc;//p指向下一个边结点
    	}
    }

*用邻接表表示图：查找每个结点的邻接点的时间复杂度为O（e),加上初始化visited数组时间复杂度O(n),DFS的时间复杂度为O(n+e)*

### 3、非连通图的深度优先搜索遍历 ###

> 算法思想：  
> 1、将图中每个顶点的访问标志设为false  
> 2、依次（顶点编号）搜索图中每个顶点，如果未被访问，则以该顶点为起点，进行深度优先搜索遍历，否则继续检查下一个顶点，直至图中所有顶点都被访问。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]

/*非连通图G的深度优先搜索遍历*/
    void DFSTraverse(Graph G)
    {
        
    	for (v = 0;v < G.vexnum;++v)
    		visited[v] = false;//访问标志数组初始化
    	for (v = 0;v < G.vexnum;++v)
    		if (!visited[v])
    			DFS(G, v);//对尚未访问的顶点调用DFS
    }

# 三、广度优先搜索BFS(Breadth First Search) #

### 1、介绍 ###

**类似于树的按层次遍历  
1、从图中某个顶点v出发，访问v  
2、依次访问v的各个未被访问过的邻接点  
3、分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点” 被访问  
4、重复3，直到所有已被访问的顶点的邻接点都被访问到。**

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

### 2、算法思想和描述 ###

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

/*按广度优先非递归遍历连通图G*/
    void BFS(Graph G, int v)
    {
        
    	cout << v;visited[v] = true;//访问第v个顶点
    	InitQueue(Q);//辅助队列Q初始化，置空
    	EnQueue(Q, v);//v进队
    	while (!QueueEmpty(Q))//队列非空
    	{
        
    		DeQueue(Q, u);//队头元素出队并置为u
    		for (w = FirstAdjVex(G, u);w>=0;w=NextAdjVex(G,u,w))
    			if (!visited[w])//w为u的尚未访问的邻接顶点
    			{
        
    				cout << w;visited[w] = true;//置访问标志数组分量为true
    				EnQueue(Q, w);//w进队
    			}
    	}
    }

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

**对无向连通图：如果将一次广度优先搜索时前进操作经过的边保留下来则可构成一棵广度优先搜索生成树。**  
![在这里插入图片描述][20201110204527859.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/dc52fa32058d4842b415d1c698610eeb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201109182241866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201109235113272.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201110151049934.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2020111015261818.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/2020111015265257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201110153930457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201110202403650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201110204304359.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[20201110204527859.png_pic_center]: https://img-blog.csdnimg.cn/20201110204527859.png#pic_center