1、深度优先搜索遍历过程
图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程
深度优先遍历特点是，选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。
2、示例
对图7-25连通无向图采用深度优先搜索遍历可得到顶点访问序列：v0,v1,v3,v7,v4,v8,v2,v5,v6
对图7-26连通无向图采用深度优先搜索遍历可得到顶点访问序列：v0,v1,v3,v2,v4,v5,v6,v7
对图7-27连通无向图采用深度优先搜索遍历可得到顶点访问序列:v0,v1,v4,v3,v2或v2,v3,v0,v1,v4或v2,v1,v0,v4,v3
3、连通图的深度优先遍历
给定一图G=<V,E>，用visited[i]表示顶点i的访问情况，初值设为0，表示所有顶点未被访问过，当顶点被访问过时置1。则初始情况下所有的visited[i]都为0。假设从顶点V0开始遍历，则下一个遍历的顶点是V0的第一个邻接点Vi，接着遍历Vi的第一个邻接点Vj，……直到所有的顶点都被访过。
4、代码
无向图，邻接矩阵存储：
对图7-25深度优先遍历：
无向图，邻接表存储：
图7-25：
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/6757.html