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

《计算机统考重难点班讲义(数据结构)-第三讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义(数据结构)-第三讲.ppt（45页珍藏版）》请在三一办公上搜索。

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

2、Type*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的入边邻接点,无向图邻接矩阵的特点：对称矩阵顶点Vi的度等于第i行非零

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

4、找一个顶点的出边容易，找入边需要遍历整个邻接表边结点的个数等于边数,深度优先搜索遍历(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访问序列：,V3,V2,V4,V9,V1,V6,V5,V2,V4,V3

5、,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,V4,BFS遍历过程：从图G的某个顶点v出发，访问v；依次访问V的未被

6、访问的邻接点；再按照“先被访问顶点的邻接点先访问”的次序，依次访问这些邻接点的邻接点，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中还有顶点未曾被访问，则另选一个未被访问的顶点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,V5,4,V4,3,V3,2,V2,1,V1,0,firstarc,求无向图

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

8、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条连接蓝点的紫边。从紫边集中选一条最小的紫边，将相应的蓝点Vj变成红点。检测剩余蓝点到新红点Vj的边是否小于原来的紫边。若小，则用蓝点到新

9、红点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并入红点集；调整蓝点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

10、,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,选中最小紫边（E,G)；G并入红点集；最小生成树构造完毕,0,0,0,Kruskal算法：,A,B,C,D,E,F,A,F,E,G

11、,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【解析】无向图中，如果每个顶点都有到其它所有顶点的路径，那么这个无向图是连通图。这个题是要保证图G在任何情况下都是连通的所需要的最少边数，关键是要把握“在任何情况下都是连通的”。在顶点固定的情况下，全连通图用的边最多。极端情况是所有的边都被用于将部分顶点连接成全连通图，而另

12、一个部分顶点被孤立。15条边能够保证6个顶点的无向图成为全连通图，所以若只有15条边，则可能出现6个顶点全连通而第7个顶点被孤立的情况。再加上一条边就能保证7个顶点的无向图在任何情况下的连通性，所以答案是C，最少加数是16条。,42,对下图进行拓扑排序，可以得到不同拓扑序列的个数是A.4 B.3 C.2 D.1【解析】拓扑排序是指有向无环图中各顶点构成的有序序列。拓扑排序的步骤为：(1)在有向图中选一个没有前驱的顶点并且输出之；(2)从图中删除除该顶点和所以以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。根据拓扑排序的构造方法，该图中的拓扑排序有abced、aebcd、abecd三个。,43,命题思路7：考察图的遍历与应用，多为综合题,1.下面是用邻接表存储的图，画出此图，并写出：【西电2005】(1)从A点开始根据该邻接表按深度优先遍历该图的结果。(2)从A点开始根据该邻接表拓扑排序该图的结果,44,解析(1)深度优先遍历结果：A-B-C-H-D-E-F-G(2)拓扑排序结果：A B D C E G H F,45,