|
深度优先遍历序列 对图进行深度优先遍历时按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列或简称为DFS序列 ()一个图的DFS序列不一定惟一 当从某顶点x出发搜索时若x的邻接点有多个尚未访问过则我们可任选一个访问之 ()源点和存储结构的内容均已确定的图的DFS序列惟一 ① 邻接矩阵表示的图确定源点后DFS序列惟一 DFSM算法中当从v i 出发搜索时是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点若这样 的邻接点多于一个则选中的总是序号较小的那一个 【例】对连通图G 用邻接矩阵表示时以v 为初始出发点的 DFS遍历过程如下图(a)所示具体算法的执行过程【 参见动 画演示 】DFS序列是v v v v v v v v ②只有给出了邻接表的内容及初始出发点才能惟一确定其DFS序列 邻接表作为给定图的存储结构时其表示不惟一因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关 因此只有给出了邻接表的内容及初始出发点才能惟一确定其DFS序列 【例】连通图G 用邻接表表示时以v 为初始出发点的 DFS算法的执行过程和DFS序列【 参见动画演示 】 ( )栈在深度优先遍历算法中的作用 深度优先遍历过程中后访问的顶点其邻接点被先访问故在递归调用过程中使用栈(系统运行时刻栈)来保存已访问的顶点 算法分析 对于具有n个顶点和e条边的无向图或有向图遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM从DFSTraverse中调用 DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n 当访问某顶点v i 时DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上用邻接矩阵表示图时其搜索时间为 O(n);用邻接表表示图时需搜索第i个边表上的所有结点因此对所有n个顶点访问在邻接矩阵上共需检查n 个矩阵元素 在邻接表上需将边表中所有O(e)个结点检查一遍 所以DFSTraverse的时间复杂度为O(n ) (调用DFSM)或(n+e)(调用DFS) |
