数据结构复习与习题解析.pptx

数据结构与算法复习与习题解析(第6-8讲）

第6讲图12/04/20252图的相关定义(无向完全图、有向完全图、网、连通图、强连通图、度、入度、出度、生成树和生成森林)图的存储方式邻接矩阵无向图邻接矩阵有向图邻接矩阵网的邻接矩阵每个结点的出度？入度？度？图的边数？邻接表每个结点的出度？入度？度？图的边数？

例已知某网的邻接（出边）表，请画出该网络。当邻接表的存储结构形成后，图便唯一确定！例题解析12/04/20253

图的遍历12/04/20254广度优先搜索从图的某一结点出发，首先依次访问该结点的所有邻接顶点V1,V2,…,Vn再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。深度优先搜索1、访问指定的起始顶点；2、若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；3、若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转2；反之，遍历结束。

例题解析12/04/20255熟悉图的存储结构，画出右边有向图的邻接矩阵、邻接表、逆邻接表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF邻接矩阵如下邻接表如下逆邻接表如下【答】

最小生成树12/04/20256将顶点进行归并普里姆（Prim）算法01将边进行归并克鲁斯卡尔（Kruscal）算法02

例：Prim算法12/04/20257最小代价生成树的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V515342(4)(1)(3)(2)(5)

例：Kruscal算法12/04/20258实例的执行过程图G1、初始连通分量：{0},{1},{2},{3},{4},{5}2、反复执行添加、放弃动作。条件：边数不等于n-1时边 动作 连通分量(0,2)添加 {0,2},{1},{3},{4},{5}(3,5)添加 {0,2},{3,5},{1},{4}(1,4)添加 {0,2},{3,5},{1,4}(2,5)添加 {0,2,3,5},{1,4}(0,3)放弃 因构成回路(2,3)放弃 因构成回路(1,2)添加 {0,2,3,5,1,4}最小代价生成树V0V1V3V2V4V56165556342V0V1V3V2V4例题解析12/04/20259请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。

例题解析12/04/202510【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。

例题解析12/04/202511【解析】Kruscal算法的操作步骤：首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。

单源最短路径12/04/202512在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。迪杰斯特拉(Dijkstra)算法： 按路径长度递增次序产生最短路径1、把V分成两组：(1)S：已求出最短路径的顶点的集合。(2)V-S=T：尚未确定最短路径的顶点集合。2、将T中顶点按最短路径递增的次序加入到S中，保证：(1)从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。(2)每个顶点对应一个距离值：S中顶点：从v0到此顶点的最短路径长度。T中顶点：从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度。

Dijkstra算法步骤：T中顶点对应的距离值用辅助数组D存放。D[i]初值：若v0,vi存在，则为其权值；否则为∞。终点从v0到各终点的最短路径及长度i=1i=2i=3i=4i=5i=6v1v2v3v4v5v6vjPv5v1v6v4v3v2v08562302138∞30∞3232v3v1v11313302220v3