TIP

本文主要是介绍 图-遍历深度优先(DFS) 。

• 深度优先遍历
  • 示意图
  • 源代码参考
• 参考文章

深度优先遍历

深度优先遍历（Depth_First_Search）,也称为深度优先搜索，简称DFS，它从图中某个顶点v出发，访问此顶点，然后从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到。这里我们将到的是连通图（任意两个顶点之间都有路径）

举个例子：

示意图

我们来走一遍这个例子，首先我们从A点出发，我们给自己定一个原则，在没有碰到重复顶点的情况下，始终向右手边走。于是我们依据右手通行原则，走到了B顶点，然后再走到了C顶点，继续走又走到了D顶点，接着又走到了E顶点，接着又走到F顶点，在F点我们发现右手边是A点，是已经访问过的点，于是我们走到了G顶点，在G点发现B、D两点都已经访问过了，于是走到H点，到了H点后发现没有没被访问过的点，退回到G点，G点也没有，所以退回F点，F点一样没有，所以退回到E点，E一样，再退回到D点，到了D点还有I点没有被访问过,走到I点，到了I点发现没有没被访问过的点，退回到D点，D点也没有，退回到C点，C点也没有，退回到B点，B点也没有，退回到A点。A点也没有。此时遍历过程结束。

通过这个例子应该可以清楚了深度优先遍历的步骤。本质上就是利用了递归。

源代码参考

下面是邻接矩阵的深度优先遍历操作代码：

void DFS(MGraph G,int i)    //深度优先遍历算法
{
	visited[i]=1;
	printf("%c",G.vexs[i]);
	for (int j = 0; j < G.NumVexs; j++)
	{
		if (G.arc[i][j] == 1 && !visited[j])	//如果i点的邻接点j没有被访问过，则对该邻接点进行递归调用。
		{
			DFS(G, j);
		}
	}
}



void DFSTraverse(MGraph G)   //深度优先遍历过程
{
	for (int i = 0; i < G.NumVexs; i++)		//初始时，将所有顶点标记为未访问
	{
		visited[i] = 0;
	}
	for (int i = 0; i < G.NumVexs; i++)
	{
		if (!visited[i])					//如果该顶点未访问，调用DFS
		{
			DFS(G, i);
		}
	}
}

我们通过代码可以看到，深度优先遍历就用到了递归。

参考文章

• https://blog.csdn.net/weixin_43977523/article/details/89402161