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的尚未访问的邻接顶点 } } } 注意：图的邻接矩阵表示是唯一的，但对于邻接表来说