5.3.2 深度优先搜索（Depth-First-Search，DFS）

与广度优先搜索不同，深度优先搜索（DFS）类似于树的先序遍历。正如其名称中所暗含的意思一样，这种搜索所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未访问的任一顶点W1，再访问与w1邻接且未被访问任一W2，……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始上述搜索过程，直到图中所有顶点均被访问过止。

bool visited[MAX-VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G){
//对图中G进行深度优先遍历，访问函数为visit()
	for(v=0;v<G.vexnum;v++)
		visited[v]=false;//初始化已访问标记数据
	for(v=0;v<G.vexnum;v++)
        	if(!visited[v])
        		DFS(G,v);
	}
}
void DFS(Graph G，intv){
//从顶点v出发，采用递归思想，深度优先遍历图G
	visit(v);//访问顶点v
	visited[v]=TRUE;//设已访问标记
	for(w=firstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w)){
		if(!visited[w]){
			DFS(G,w);//w为u的尚未访问的邻接顶点
		}	
	}          
}

注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，如果边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

1、DFS算法的性能分析

DFS算法是一个递归算法，需要一个递归工作栈，故它的空间复杂度为O(|v|)。

遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储机构。当以邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(|v|)，故总的时间复杂度为O（|v|^2）。当以邻接表表示时，查找所有顶点的邻接表所需时间为O(|E|)，访问顶点所需时间为O(|v|)，此时，总的时间复杂度为O(|v|+|E|)。

2、深度优先的生成树和生成森林

与关固定优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，这是由条件的，即对连通图调用DFS才可以产生深度优先生成树，否则产生的将是深度优先生成森林。和BFS类似，基于邻接表存储的深度优先生成树是不唯一的。