数据结构——图——深度优先遍历

本是古典何须时尚 2023-01-11 08:34 117阅读 0赞

## 数据结构——图——深度优先遍历 ##

深度优先遍历（Depth\_First\_Search)，也有称为深度优先搜索，简称为DFS。它的具体思想就如同我刚才提到的找钥匙方案，无论从哪一间房间开始都可以，比如主卧室，然后从房间的一个角开始，将房间内的墙角、床头柜、床上、床下、衣柜里、衣柜上、前面的电视柜等挨个寻找，做到不放过任何一个死角，所有的抽屉、储藏柜中全部都找遍，形象比喻就是翻个底朝天，然后再寻找下一间，直到找到为止。

为了更好的理解深度优先遍历，我们来做一个游戏。

假设你需要完成一个任务，要求你在如图7-5-2左图这样的一个迷宫中，从顶点A开始要走遍所有的图顶点并作上标记，注意不是简单地看着这样的平面图走哦，而是如同现实般地在只有高墙和通道的迷宫中去完成任务。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
很显然我们是需要策略的，否则在这四通八达的通道中乱窜，要想完成任务那就只能是碰运气。如果你学过深度优先遍历，这个任务就不难完成了。

首先我们从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F，我们给自己定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看图7-5-2的右图。此时发现有三条分支，分别通向顶点C、I、G，右手通行原则，使得我们走到了C顶点。就这样，我们一直顺着右手通道走，一直走到F顶点。当我们依然选择右手通道走过去后，发现走回到顶点A了，因为在这里做了记号表示已经走过。此时我们退回到顶点F，走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H，当我们面对通向H的两条通道D和E时，会发现都已经走过了。

此时我们是否已经遍历了所有顶点呢?没有。可能还有很多分支的顶点我们没有走到，所以我们按原路返回。在顶点H处，再无通道没走过，返回到G，也无未走过通道，返回到F，没有通道，返回到E，有一条通道通往H的通道，验证后也是走过的，再返回到顶点D，此时还有三条道未走过，一条条来，H走过了，G走过了，1，哦，这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点A，确认你已经完成遍历任务，找到了所有的9个顶点。

反应快的同学一定会感觉到，深度优先遍历其实就是一个递归的过程，如果再敏感一些，会发现其实转换成如图7-5-2的右图后，就像是一棵树的前序遍历，没错，它就是。它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。事实上，我们这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

如果我们用的是邻接矩阵的方式，则代码如下:

/*邻接矩阵的结构*/
    typedef char VertexType;  /*顶点类型应由用户定义*/
    
    typedef int EdgeType; /*边上的权值类型应由用户定义*/
    
    #define MAXVEX 100   /*最大顶点数，应由用户定义*/
    
    #define INFINITY 65535  /*用65535来代表*/
    
    typedef struct
    {
        
    	VertexType vexs[MAXVEX];   /*顶点表*/
    	EdgeType arc[MAXVEX][MAXVEX];  /*领边矩阵，可看作边表*/
    
    	int numVertexes, numEdges;    /*图中当前的顶点数和边数*/
    } MGraph;
    
    #define TRUE 1
    #define FALSE 0
    typedef int Boolean; /*Boolean 是布尔类型， 其值是TRUE 或 FALSE*/
    
    Boolean visited[MAXVEX]; /*访问标志的数组*/
    
    /*邻接矩阵的深度优先递归算法*/
    void DFS(MGraph G,int i)
    {
        
    	int j;
    
    	visited[i] = TRUE;
    	printf("%c", G.vexs[i]);     /*打印顶点，也可以其他操作*/
    
    	for (j =0; j < G.numVertexes; j++)
    	{
        
    	    if (G.arc[i][j]==1&&!visited[j])
    	    {
        
    			DFS(G, j);    /*对为访问的邻接顶点递归调用*/
    	    }
    	}
    }
    
    /*邻接矩阵的深度遍历操作*/
    void DFSTraverse(MGraph G)
    {
        
    	int i;
    	for (i=0;i<G.numVertexes;i++)
    	{
        
    		visited[i] = FALSE;/*初始化所有顶点状态都是未访问过状态*/
    	}
    
    	for (i = 0; i < G.numVertexes; i++)
    	{
        
    		if (!visited[i]) /*对未访问过的顶点调用DFS，若是连通图，只会执行一次*/
    		{
        
    			DFS(G, i); 
    		}
    	}
    }

代码的执行过程，其实就是我们刚才迷宫找寻所有顶点的过程。

如果图结构是邻接表结构，其 DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。

#define MAXVEX 100   /*最大顶点数，应由用户定义*/
    typedef char VertexType;  /*顶点类型应由用户定义*/
    
    typedef int EdgeType;  /*边上的权值类型应由用户定义*/
    
    typedef struct EdgeNode  /*边表结点*/
    {
        
    	int adjvex;  /*邻接点域，存储该顶点对应的下标*/
    	EdgeType weight; /*用于存储权值，对于非网图可以不需要*/
    	struct EdgeNode* next;  /*链域，指向下一个邻接点*/
    } EdgeNode;
    
    typedef struct vertexNode/*顶点表结点*/
    {
        
    	VertexType data;   /*顶点域，存储顶点信息*/
    	EdgeNode* firstedge;   /*边表头指针*/
    
    }vertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
        
    	AdjList adjList;
    	int numvertexes, numEdges;/*图中当前顶点数和边数*/
    
    } GraphAdjList;
    
    #define TRUE 1
    #define FALSE 0
    typedef int Boolean; /*Boolean 是布尔类型， 其值是TRUE 或 FALSE*/
    
    Boolean visited[MAXVEX]; /*访问标志的数组*/
    
    
    /*邻接表的深度优先递归算法*/
    void DFS(GraphAdjList* GL, int i)
    {
        
    	EdgeNode* P;
    	visited[i] = TRUE;
    	printf("%c",GL->adjList[i].data);/*打印顶点，也可以其他操作*/
    	P = GL->adjList[i].firstedge;
    	while (P)
    	{
        
    		if (!visited[P->adjvex])
    		{
        
    			DFS(GL,P->adjvex);   /*对为访问的邻接顶点递归调用*/
    		}
    		P = P->next;
    	}
    }
    
    /*邻接表的深度遍历操作*/
    void DFSTraverse(GraphAdjList* GL)
    {
        
    	int i;
    	for (i=0;i< GL->numvertexes;i++)
    	{
        
    		visited[i] = FALSE;/*初始化所有顶点状态都是未访问过状态*/
    	}
    
    	for ( i = 0; i < GL->numvertexes; i++)
    	{
        
    		if (!visited[i])/*对未访问过的顶点调用DFS，若是连通图，只会执行一次*/
    		{
        
    			DFS(GL, i);
    		}
    	}
    }

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是o(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221119/d5a9ffcdbf954ea8958d1709df25c36b.png