《数据结构》 第七章下)
《 数据结构》 第七章(下)
数据结构 第七章图 71图的定义和术语 72图的存储结构 721数组表示法 7.2.2邻接表 73图的遍历 73.1深度优先搜索 7.3.2广度优先搜索 74图的连通性问题 74.3最小生成树 75有向无环图及其应用 7.5.1拓扑排序 7.6最短路径 761从某个源点到其余各顶点的最短路径 76.2每一对顶点之间的最短路径
数据结构 tjm 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 图的连通性问题 7.4.3 最小生成树 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短路径
数据结构 73的遍历 73.1深度优先搜索 方法:从图的某一顶点vo出发,访问此项点; 然后依次从v0的未被访问的邻接点出发,深度 优先遍历图,直至图中所有和V0相通的顶点都 被访问到; 若此时图中尚有顶点未被访问,则另选图中一个 未被访问的顶点作起点重复上述过程,直至图 中所有顶点都被访问为止
数据结构 tjm 7.3 图的遍历 7.3.1 深度优先搜索 方法：从图的某一顶点V0出发，访问此顶点； 然后依次从V0的未被访问的邻接点出发，深度 优先遍历图，直至图中所有和V0相通的顶点都 被访问到； 若此时图中尚有顶点未被访问，则另选图中一个 未被访问的顶点作起点,重复上述过程，直至图 中所有顶点都被访问为止
数据结构 深度优先遍历算法(递归算法)参见P169。 例 深度遍历:Ⅵ1→V2→V4→V8→V5→V3→V6→V7 3 v8 V5 深度优先生成树
数据结构 tjm V1 V2 V4 V5 V3 V6 V7 V8 例： 深度遍历：V1 V2 V4 V8 V5 V3 V6 V7 深度优先遍历算法（递归算法）参见P169。 V1 V2 V4 V5 V3 V7 V6 V8 深度优先生成树 V1 V2 V4 V5 V3 V6 V7 V8
数据结构 例: s97 v8 vexdata firstarc adtvexnexta 2345678 2345678 35788765 24622334 深度遍历:V1→V3→V7→V6→V2→V5→V8→V4
数据结构 tjm V1 V2 V4 V5 V3 V6 V7 V8 例： 1 2 3 4 1 3 4 2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvexnextarc 5 5 6 5 4 1 ^ 1 2 8 2 ^ 6 7 8 6 7 8 7 3 6 3 5 4 ^ ^ ^ 深度遍历：V1V3 V7 V6 V2 V5 V8 V4