图的深度优先遍历

图的深度优先遍历
1、深度优先搜索遍历过程
图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程
深度优先遍历特点是，选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。
示例

对图7-25连通无向图采用深度优先搜索遍历可得到顶点访问序列：v0,v1,v3,v7,v4,v8,v2,v5,v6

对图7-26连通无向图采用深度优先搜索遍历可得到顶点访问序列：v0,v1,v3,v2,v4,v5,v6,v7
连通图的深度优先遍历
给定一图G=，用visited[i]表示顶点i的访问情况，初值设为0，表示所有顶点未被访问过，当顶点被访问过时置1。则初始情况下所有的visited[i]都为0。假设从顶点V0开始遍历，则下一个遍历的顶点是V0的第一个邻接点Vi，接着遍历Vi的第一个邻接点Vj，……直到所有的顶点都被访过。
图的深度优先遍历与连通分量的个数的关系
通过深度优先遍历可以得到无向图的连通分量。
图的深度优先遍历是图论算法的基础算法，许多算法都可以用深度优先的思想进行设计。
练习题
P5318 【深基18.例3】查找文献 普及/提高-
P1807 最长路 普及/提高-
P3916 图的遍历普及/提高