计算机统考重难点班讲义数据结构-第三讲

1、数据结构 重难点串讲,讲师：翔高教育一级培训师 地点：上海,第5章 图,重难点导航,图的存储结构，尤其是邻接矩阵和邻接表 图的遍历算法；广度优先搜索遍历和深度优先搜索遍历。图的遍历是图各种运算的基础 最小生成树的生成算法以及过程，熟练掌握Prim和Kruskal算法，特别是利用两算法手工模拟生成树的生成过程 图的应用：最小生成树，拓扑排序，关键路径，最短路径,3,邻接矩阵表示法(数组表示法),用一个一维数组存放图的顶点数据 用一个矩阵Ann来存放图的边的信息:,图的邻接矩阵定义： typedef struct /弧结点与矩阵的类型 VRType adj; /VRType为弧的类型。图-0,1;

2、网-权值 InfoType *Info; /与弧相关的信息的指针,可省略 ArcCell, AdjMatrixmax_nmax_n; typedef struct/图的类型 VertexType vexsmax_n;/顶点向量 AdjMatrix arcs;/邻接矩阵 int vexnum, arcnum;/顶点数，边数 GraphKind kind；/图类型 MGraph;,G.arcs=,G.vexs=,无向图的邻接矩阵,存放顶点的数组,表示边的矩阵,G.arcs=,G.vexs=,有向图的邻接矩阵,存放顶点的数组,表示弧的矩阵,V4的出边邻接点,V4的入边邻接点,无向图邻接矩阵的特点：

3、对称矩阵 顶点Vi的度等于第i行非零元个数，或第i列非零元个数： 矩阵非零元总数等于边数的2倍,有向图邻接矩阵的特点： 是非对称矩阵 第i行非零元个数等于顶点Vi的出度；第i列非零元个数等于顶点Vi的入度： 矩阵非零元总数等于边数,G.arcs=,G.vexs=,有向网的邻接矩阵示例：,7.2.1 邻接表表示法 将每个顶点的邻接点串成一个单链表：,边结点,顶点结点,firstarc,G.vertices,无向图的邻接表：,无向图邻接表的特点： 顶点Vi的度等于Vi所引导的单链表的长度 边结点的个数等于边数的2倍,有向图的邻接表：,firstarc,G.vertices,有向图邻接表的特点： 顶

4、点Vi引导的单链表是出边链，链表的长度等于Vi的出度 找一个顶点的出边容易，找入边需要遍历整个邻接表 边结点的个数等于边数,深度优先搜索遍历(DFS),Depth First Search; 类似于树的先根遍历; 优先向纵深访问,DFS遍历过程： 从图G中选某个顶点V作为出发点； 访问V； 依次从V的未被访问的邻接点出发，深度优先搜索遍历图G, 直至与V相通的顶点都被访问完； 如果此时图G中还有顶点未曾被访问，则从这些未被访问的顶点中再选一个顶点V，转2，继续遍历；否则遍历结束。,V1,V7,V4,V3,V5,V6,V2,DFS访问序列：,V1,V2,V5,V6,V7,V3,V4,V1,DFS

5、访问序列：,V3,V2,V4,V9,V1,V6,V5,V2,V4,V3,V6,V5,V8,V7,V9,V8,V7,V8,V3,V1,V7,V4,V9,V5,V6,V2,DFS访问序列：,V1,V9,V7,V2,V5,V6,V4,data,8,7,V7,6,V6,5,V5,4,V4,3,V9,2,V2,1,V1,0,firstarc,V8,V3,V3,V8,V1,V7,V4,V3,V5,V6,V2,V8,data,8,V8,7,V7,6,V6,5,V5,4,V4,3,V3,2,V2,1,V1,0,firstarc,G.vertices,DFS访问序列：,V1,V2,V3,V6,V5,V8,V7,

6、V4,BFS遍历过程： 从图G的某个顶点v出发，访问v； 依次访问V的未被访问的邻接点； 再按照“先被访问顶点的邻接点先访问”的次序，依次访问这些邻接点的邻接点，直至图中所有已被访问的顶点的邻接点都被访问到； 若此时图中还有顶点未曾被访问，则另选一个未被访问的顶点v作为出发点，重复上述过程，直至图中所有的顶点都被访问完。,V1,BFS访问序列：,V3,V2,V1,V6,V4,V5,V9,V2,V4,V3,V6,V5,V8,V7,V9,V8,V7,V1,V7,V4,V3,V5,V6,V2,V8,访问序列：,V1,V2,V4,V5,V6,V7,V8,V3,data,8,V8,7,V7,6,V6,5

7、,V5,4,V4,3,V3,2,V2,1,V1,0,firstarc,求无向图的连通分量： 对无向图G调用一次DFS过程，能访问完G的一个连通分量。因此对DFS算法稍做修改就可解决求无向图连通分量的问题。,最小生成树,最小(代价)生成树：无向网的所有生成树中，边权之和最小的生成树。 构造最小生成树的著名算法： Prim算法 Kruskal算法,在n个城市之间建通讯网； 可能的线路最多有n(n-1)/2条； 从中选择n1条，满足： (1)连通； (2)边上权值之和为最小。 这就是构造最小代价生成树。,最小生成树的MST性质： 设G(V, E)是一个连通网，U是顶点V的一个非空子集。若(u, v)

8、是一条具有最小权值的边，且uU集，vVU集，则必存在一棵包含边(u, v)的最小生成树。,V1,V2,V4,V5,V6,V3,5,6,1,3,2,6,6,5,5,4,U集(红点集),VU集(蓝点集),最小紫边一定会在G的某棵最小生成树上出现,Prim算法思想： 由于红点集与蓝点集的划分是任意的，经过n1次不同的划分，找到每次划分的最小紫边，以此来构成最小生成树的n-1条边。 在每次划分中，每个蓝点可能有多条紫边连接红点。为了简化，我们将每个蓝点用一条最小的紫边连接到红点上，构成生成树的n1条边。,初态：任选一个顶点作为红点，不妨设是V1。邻接矩阵的V1行就是n1条连接蓝点的紫边。 从紫边集中选

9、一条最小的紫边，将相应的蓝点Vj变成红点。 检测剩余蓝点到新红点Vj的边是否小于原来的紫边。若小，则用蓝点到新红点Vj的紫边取代原来的紫边,Prim算法的存储结构(1)：无向网用邻接矩阵表示,A,F,E,G,D,C,B,A,F,E,G,D,C,B,设：初态时红点集中只有一个顶点A； 邻接矩阵的第0行表示了所有的紫边,A,F,E,G,D,C,B,12,A,A,A,A,A,A,16,14,0,B,10,B,7,选中最小紫边（A,B)； B并入红点集； 调整蓝点C，F所关联的紫边,A,F,E,G,D,C,B,A,B,A,A,B,A,10,14,0,F,6,7,选中最小紫边（B,F)； F并入红点集；

10、 调整蓝点C,E,G所关联的紫边,0,F,2,9,F,A,F,E,G,D,C,B,A,F,A,F,B,F,6,2,9,0,0,选中最小紫边（F,E)； E并入红点集； 调整蓝点C,D,G所关联的紫边,0,E,5,E,4,E,8,A,F,E,G,D,C,B,A,E,E,F,B,E,5,4,16,8,0,B,0,选中最小紫边（E,D)； D并入红点集； 调整蓝点C所关联的紫边,0,D,3,0,A,F,E,G,D,C,B,A,E,E,F,B,E,3,0,8,0,0,选中最小紫边（D,C)； C并入红点集； 没有需要调整的紫边,0,0,A,F,E,G,D,C,B,A,E,E,F,B,E,0,8,0,0

11、,选中最小紫边（E,G)； G并入红点集； 最小生成树构造完毕,0,0,0,Kruskal算法：,A,B,C,D,E,F,A,F,E,G,D,C,B,G,A B C D E, F G,A B C, D E, F G,A B C, D, E, F G,A B, C, D, E, F G,A B, C, D, E, F, G,A, B, C, D, E, F, G,经典例题解析,【例1】若无向图G=(V,E)中合有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是 A6 B15 C16 D21 【解析】无向图中，如果每个顶点都有到其它所有顶点的路径，那么这个无向图是连通图。这个题是要保

12、证图G在任何情况下都是连通的所需要的最少边数，关键是要把握“在任何情况下都是连通的”。在顶点固定的情况下，全连通图用的边最多。极端情况是所有的边都被用于将部分顶点连接成全连通图，而另一个部分顶点被孤立。15条边能够保证6个顶点的无向图成为全连通图，所以若只有15条边，则可能出现6个顶点全连通而第7个顶点被孤立的情况。再加上一条边就能保证7个顶点的无向图在任何情况下的连通性，所以答案是C，最少加数是16条。,42,对下图进行拓扑排序，可以得到不同拓扑序列的个数是 A. 4 B. 3 C. 2 D. 1 【解析】拓扑排序是指有向无环图中各顶点构成的有序序列。 拓扑排序的步骤为：(1 )在有向图中选一个没有前驱的顶点并且输出之； (2)从图中删除除该顶点和所以以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。根据拓扑排序的构造方法，该图中的拓扑排序有