图 - 图的遍历 - 深度优先遍历（三）
深度优先遍历序列
对图进行深度优先遍历时 按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列 或简称为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)
lishixinzhi/Article/program/sjjg/201311/23835
