图的遍历 ——深度优先遍历

深度优先搜索（Depth First Search，DFS）是最常见的图搜索方法之一。

深度优先搜索沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。深度优先遍历是按照深度优先搜索的方式对图进行遍历的。

深度优先遍历的秘籍：后被访问的节点，其邻接点先被访问。

根据深度优先遍历的秘籍，后来者先服务，这可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归的方法更方便。

【算法步骤】

① 初始化图中的所有节点均未被访问。

② 从图中的某个节点v 出发，访问v 并标记其已被访问。

③ 依次检查v 的所有邻接点w ，如果w 未被访问，则从w 出发进行深度优先遍历（递归调用，重复步骤2～3）。

【完美图解】

例如，一个无向图如下图所示，

其深度优先遍历的过程如下所述。

① 初始化所有节点均未被访问，visited[i]=false，i =1,2,…,8。

② 从节点1出发，标记其已被访问，visited[1]=true。

③ 从节点1出发访问邻接点2，然后从节点2出发访问节点4，从节点4出发访问节点5，从节点5出发访问未被访问的邻接点。

④ 回退到刚刚访问过的节点4，节点4也没有未被访问的邻接点，回退到最近访问过的节点2，从节点2出发访问下一个未被访问的邻接点6。

⑤ 从节点6出发访问未被访问的邻接点，回退到刚刚访问过的节点2，节点2没有未被访问的邻接点，回退到最近访问过的节点1。

⑥ 从节点1出发访问下一个未被访问的邻接点3，从节点3出发访问节点7，从节点7出发访问节点8，从节点8出发访问未被访问的邻接点。

⑦ 回退到刚刚访问过的节点7，节点7也没有未被访问的邻接点，回退到最近访问过的节点3，节点3也没有未被访问的邻接点，回退到最近访问过的节点1，节点1也没有未被访问的邻接点，遍历结束。访问路径如下图所示。

∴ 深度优先遍历序列为1 2 4 5 6 3 7 8。

深度优先遍历经过的节点及边被称为深度优先生成树，如下图所示。

如果深度优先遍历非连通图，则每一个连通分量都会产生一棵深度优先生成树。

【算法实现】

① 基于邻接矩阵的深度优先遍历

void DFS_AM(AMGragh G , int v){ //基于邻接矩阵的深度优先遍历
	cout << G.Vex[v] << "\t";
	visited[v] = true;
	for(int w = 0 ; w < G.vexnum ; w++){ //依次检查v 的所有邻接点
		if(G.Edge[v][w] && visited[w]){ //v、w 邻接并且w 未被访问
			DFS_AM(G , w); //从节点w 出发，递归深度优先遍历
		}
	}
}

② 基于邻接表的深度优先遍历

void DFS_AL(ALGragh G , int v){ //基于邻接表的深度优先遍历
	AdjNode *p;
	cout << G.Vex[v].data << "\t";
	visited[v] = true;
	p = G.Vex[v].first;
	while(p){ //依次检查v 的所有邻接点
		int w = p->v; //w 为 v 的邻接点
		if(!visited[w]){ //w未被访问
			DFS_AL(G , w); //从w 出发，递归深度优先遍历
		}
		p = p->next;
	}
}

③ 基于非连通图的深度优先遍历

void DFS_AL(ALGragh G){ //非连通图，基于邻接表的深度优先遍历
	for(int i = 0 ; i < G.vexnum ; i++){ //对非连通图需要查漏点，检查未被访问的节点
		if(!visited[i]){ //i 未被访问，以i 为起点再次广度优先遍历
			DFS_AL(G , i); //基于邻接表，也可以替换为基于邻接矩阵DFS_AM(G , i);
		}
	}
}

【算法分析】

深度优先遍历的过程实质上是对每个节点都搜索其邻接点的过程，图的存储方式不同，其算法复杂度也不同。

① 基于邻接矩阵的深度优先遍历算法。查找每个节点的邻接点需要O (n )时间，共n 个节点，总的时间复杂度为O (n^2 )。这里使用了一个递归工作栈，空间复杂度为O (n )

② 基于邻接表的深度优先遍历算法。查找节点vi 的邻接点需要O (d (vi ))时间，d (vi )为vi 的出度，对有向图而言，所有节点的出度之和等于边数e ；对无向图而言，所有节点的度之和等于2e ，因此查找邻接点的时间复杂度为O (e )，加上初始化时间O (n )，总的时间复杂度为O (n +e )。这里使用了一个递归工作栈，空间复杂度为O (n)。

需要注意的是，一个图的邻接矩阵是唯一的，因此基于邻接矩阵的广度优先级遍历或深度优先遍历的序列也是唯一的，而图的邻接表不是唯一的，边的输入顺序不同，正序或逆序建表都会影响邻接表中的邻接点顺序，因此基于邻接表的广度优先遍历或深度优先遍历的序列不是唯一的。