数据结构-图的遍历

7 3图的遍历 11计算机科学与技术第三学习小组组长 徐月婷成员 周贺华 张小米 田贵亮蔡国帅 赵辰磊 李小飞 1 算法思想 从图中的某个顶点vi出发 先访问该顶点vi 然后依次从vi的未被访问过的邻接点出发执行深度优先遍历算法 直至图中所有和vi有路径相通的顶点都被访问到为止 若此时图中还有未被访问到的顶点 即非连通图的情形 则再选图中一个未被访问过的顶点vj作为起点重复上述过程 直至图中所有顶点均被访问过为止 一 深度优先遍历 一 深度优先遍历 2 实例 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 设从v1出发 则有遍历序列 v1 v2 v4 v8 v5 v3 v6 v7 再从另一个连通子图中选择一个还未被访问的顶点v9 并从v9出发重复上述过程有遍历序列 v9v11v10 从而有遍历序列 v1v2v4v8v5v3v6v7v9v11v10 一 深度优先遍历 3 算法 主函数 Booleanvisited MAX Status VisitFunc intv VoidDFStraverse GraphG Status Visit intv VisitFunc Visit for v 0 v G vexnum v visited v FALSE for v 0 v G vexnum v if visited v DFS G v 一 深度优先遍历 3 算法 深度遍历算法DFS的实现 voidDFS GraphG intv 从第v个顶点出发递归的深度优先遍历图Gvisited v TRUE VisitFunc v 访问第v个顶点for w FirstAdjVex G v w 0 w NextAdjVex G v w If visited w DFS G w 对v的尚未访问的邻接顶点w递归调用DFS 一 深度优先遍历 3 算法 深度遍历算法DFS的实现 voidDFS ALGraphG inti visited i TRUE printf G vertices i data 访问 即打印 i号结点for j FirstAdjVex G i j 1 j NextAdjVex G i j if visited j DFS G j 依次从i号顶点的第一个邻接点 第二个邻接点 出发深度优先遍历图 DFS 求i号顶点的第一个邻接点的序号 p G vertices i firstarc if p j p adjvex elsej 1 returnj 一 深度优先遍历 3 算法 深度遍历算法DFS的实现 voidDFS ALGraphG inti visited i TRUE printf G vertices i data 访问 即打印 i号结点for j FirstAdjVex G i j 1 j NextAdjVex G i j if visited j DFS G j 依次从i号顶点的第一个邻接点 第二个邻接点 出发深度优先遍历图 DFS 求i号顶点的处于序号为j的邻接点的后面的 再下一个邻接点 的序号 p G vertices i firstarc while p 二 广度优先遍历 1 算法思想 从图中的某个顶点vi出发 先访问该顶点vi 然后依次访问vi的各个未曾访问过的邻接点 然后再依次访问这些邻接点的邻接点 重复上述过程 直至图中所有和vi有路径相通的顶点都被访问到为止 若此时图中还有未被访问到的顶点 即非连通图的情形 则再选图中一个未被访问过的顶点vj作为起点重复上述过程 直至图中所有顶点均被访问过为止 2 实例 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 设从v1出发 则有遍历序列 v10 v2 v3 v4 v5 v6 v7 v8 再从另一个连通子图中选择一个还未被访问的顶点v10 并从v10出发重复上述过程有遍历序列 从而有遍历序列 v1v2v3v4v5v6v7v8v10v9v11 二 广度优先遍历 v9 v11 v1 3 广度优先遍历算法的实现 非递归编程方法 voidBFStraverse ALGraphG Booleanvisited G vexnum intv u w for v 0 v 1 w NextAdjVex G u w