《计算机统考重难点班讲义(数据结构)-第三讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义(数据结构)-第三讲.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构重难点串讲重难点串讲讲师：翔高教育一级培训师地点：上海第第5 5章章 图图重难点导航重难点导航v图的存储结构，尤其是邻接矩阵和邻接表图的存储结构，尤其是邻接矩阵和邻接表v图的遍历算法；广度优先搜索遍历和深度优先搜索图的遍历算法；广度优先搜索遍历和深度优先搜索遍历。图的遍历是图各种运算的基础遍历。图的遍历是图各种运算的基础v最小生成树的生成算法以及过程，熟练掌握最小生成树的生成算法以及过程，熟练掌握PrimPrim和和KruskalKruskal算法，特别是利用两算法手工模拟生成树算法，特别是利用两算法手工模拟生成树的生成过程的生成过程v图的应用：最小生成树，拓扑排序，关键路径，
2、最图的应用：最小生成树，拓扑排序，关键路径，最短路径短路径3邻接矩阵表示法邻接矩阵表示法(数组表示法数组表示法)用一个一维数组存放图的顶点数据用一个一维数组存放图的顶点数据用一个矩阵用一个矩阵Ann来存放图的边的信息来存放图的边的信息:有向有向/无向图无向图:A i j 0 0 反之反之1 若若 或或(Vi,Vj)E(G)有向有向/无向网无向网:A i j 或或 0 0 反之反之wij 若若 或或(Vi,Vj)E(G)图的邻接矩阵定义：图的邻接矩阵定义：typedef struct/弧结点与矩阵的类型弧结点与矩阵的类型 VRType adj;/VRType/VRType为弧的类型。图为弧的类型
3、。图-0,1;-0,1;网网-权值权值 InfoType *Info;/与弧相关的信息的指针与弧相关的信息的指针,可省略可省略ArcCell,AdjMatrixmax_nmax_n;typedef struct/图的类型图的类型 VertexType vexsmax_n;/顶点向量顶点向量 AdjMatrix arcs;/邻接矩阵邻接矩阵 int vexnum,arcnum;/顶点数，边数顶点数，边数 GraphKind kind；/图类型图类型MGraph;V1V7V4V3V5V6V2V1V2V3V4V5V6V70123456012345600111000110001112100000131
4、000000401000105010010060110000G.arcs=G.vexs=无向图的邻接矩无向图的邻接矩阵阵存放顶点的数组表示边的矩阵V1V2V3V4V5V6V7V80123456701234567001110000100101100200000100300100110400000001500001010600000001700000000G.arcs=G.vexs=V1V7V4V3V5V6V2V8有向图的邻接矩有向图的邻接矩阵阵存放顶点的数组存放顶点的数组表示弧的矩阵表示弧的矩阵V4的出边邻接点V4的入边邻接点无无向图邻接矩阵的特点：向图邻接矩阵的特点：8对称矩阵对称矩阵8顶点顶
5、点ViVi的度等于第的度等于第i i行非零元个数，或第行非零元个数，或第i i列非零列非零元个数：元个数：8矩阵非零元总数等于边数的矩阵非零元总数等于边数的2 2倍倍 有向图邻接矩阵的特点：有向图邻接矩阵的特点：8是非对称矩阵是非对称矩阵8第第i i行非零元个数等于顶点行非零元个数等于顶点ViVi的出度；第的出度；第i i列非零列非零元个数等于顶点元个数等于顶点ViVi的入度：的入度：8矩阵非零元总数等于边数矩阵非零元总数等于边数 ABCD01230123014192235836G.arcs=G.vexs=有向网的邻接矩阵示例：有向网的邻接矩阵示例：68314592ADCB7.2.1 邻接表表
6、示法邻接表表示法将每个顶点的邻接点串成一个单链表：将每个顶点的邻接点串成一个单链表：邻接点邻接点后继指针后继指针 边信息指针边信息指针顶点数据顶点数据边链头指针边链头指针adjvex nextarcinfodatafirstarc边结点边结点顶点结点顶点结点V1V7V4V3V5V6V2data0V11V22V33V44V55V66V7891321546010firstarc645021G.vertices无向图的邻接表：无向图的邻接表：adjvex nextarc无向图邻接表的特点：无向图邻接表的特点：8顶点顶点ViVi的度等于的度等于ViVi所引导的单链表的长度所引导的单链表的长度8边结点的
7、个数等于边数的边结点的个数等于边数的2 2倍倍 有向图的邻接表：V1V7V4V3V5V6V2V8data0V11V22V33V44V55V66V78V891 32 7 6 54firstarcadjvex nextarc54 2 724 5G.vertices有向图邻接表的特点：8顶点顶点Vi引导的单链表是出边链，链表的长度等引导的单链表是出边链，链表的长度等于于Vi的出度的出度8找一个顶点的出边容易，找入边需要遍历整个找一个顶点的出边容易，找入边需要遍历整个邻接表邻接表8边结点的个数等于边数边结点的个数等于边数深度优先搜索遍历深度优先搜索遍历(DFS)(DFS)8Depth First Se
8、arch;8类似于树的先根遍历类似于树的先根遍历;8优先向纵深访问优先向纵深访问DFSDFS遍历过程：遍历过程：1.1.从图从图G G中选某个顶点中选某个顶点V V作为出发点；作为出发点；2.2.访问访问V V；3.3.依次从依次从V V的未被访问的邻接点出发，深度优先搜的未被访问的邻接点出发，深度优先搜索遍历图索遍历图G,G,直至与直至与V V相通的顶点都被访问完；相通的顶点都被访问完；4.4.如果此时图如果此时图G G中还有顶点未曾被访问，则从这些中还有顶点未曾被访问，则从这些未被访问的顶点中再选一个顶点未被访问的顶点中再选一个顶点V V，转，转2 2，继续遍，继续遍历；否则遍历结束历；否
9、则遍历结束。V1V7V4V3V5V6V2出发点DFS访问序列：V1V2V5V6V7V3V4V1出发点出发点DFSDFS访问序列：访问序列：V3V2V4V9V1V6V5V2V4V3V6V5V8V7V9V8V7V8V3V1V7V4V9V5V6V2出发点出发点DFS访问序列：访问序列：V1V9V7V2V5V6V4data87V76V65V54V43V92V21V108311546012firstarc054681V8V370V3V8V1V7V4V3V5V6V2V8data8V87V76V65V54V43V32V21V101327654firstarc2457256G.verticesDFS访问序列：
10、访问序列：V1V2V3V6V5V8V7V4出发点出发点BFSBFS遍历过程：遍历过程：1.1.从图从图G G的某个顶点的某个顶点v v出发，访问出发，访问v v；2.2.依次依次访问访问V V的未被访问的邻接点；的未被访问的邻接点；3.3.再按照再按照“先被访问顶点的邻接点先访问先被访问顶点的邻接点先访问”的次序，依次的次序，依次访问这些邻接点的邻接点，直至图中所有已被访访问这些邻接点的邻接点，直至图中所有已被访问的顶点的邻接点都被访问到；问的顶点的邻接点都被访问到；4.4.若此时图中还有顶点未曾被访问，则另选一个未若此时图中还有顶点未曾被访问，则另选一个未被访问的顶点被访问的顶点v v作为出
11、发点，重复上述过程，直至作为出发点，重复上述过程，直至图中所有的顶点都被访问完。图中所有的顶点都被访问完。V1出发点出发点BFSBFS访问序列：访问序列：V3V2V1V6V4V5V9V2V4V3V6V5V8V7V9V8V7V1V7V4V3V5V6V2V8访问序列：访问序列：V1V2V4V5V6V7V8出发点V3data8V87V76V65V54V43V32V21V101327654firstarc2457256求无向图的连通分量：求无向图的连通分量：对无向图对无向图G调用一次调用一次DFS过程，能访问完过程，能访问完G的一的一个连通分量。因此对个连通分量。因此对DFS算法稍做修改就可解决求算法
12、稍做修改就可解决求无向图连通分量的问题无向图连通分量的问题。最小生成树最小生成树8最小最小(代价代价)生成树：生成树：无向网的所有生成树中，无向网的所有生成树中，边权之和最小的生成树。边权之和最小的生成树。8构造最小生成树的著名算法：构造最小生成树的著名算法：PrimPrim算法算法 KruskalKruskal算法算法8在在n个城市之间建通讯网；个城市之间建通讯网；8可能的线路最多有可能的线路最多有n(n-1)/2条；条；8从中选择从中选择n1条，满足：条，满足：(1)连通；连通；(2)边上权值之和为最小。边上权值之和为最小。8这就是构造这就是构造最小代价生成树最小代价生成树。V1V2V4V
13、5V6V35613266554最小生成树的最小生成树的MSTMST性质性质：设设G G(V,E)(V,E)是一个连通网，是一个连通网，U U是顶点是顶点V V的一个非空子的一个非空子集。若集。若(u,v)(u,v)是一条具有是一条具有最小权值的边最小权值的边，且，且u u U U集，集，v v V VU U集，则必存在一棵包含边集，则必存在一棵包含边(u,v)(u,v)的最小生成树。的最小生成树。V1V2V4V5V6V35613266554U集(红点集)VU集(蓝点集)联接红点和蓝点的边(紫边)最小紫边一定会最小紫边一定会在在G G的某棵最小的某棵最小生成树上出现生成树上出现PrimPrim算
14、法思想：算法思想：8由于红点集与蓝点集的划分是任意的，经过由于红点集与蓝点集的划分是任意的，经过n n1 1次不同的划分，找到每次划分的最小紫边，以此次不同的划分，找到每次划分的最小紫边，以此来构成最小生成树的来构成最小生成树的n-1n-1条边。条边。8在每次划分中，每个蓝点可能有多条紫边连接红在每次划分中，每个蓝点可能有多条紫边连接红点。为了简化，我们将每个蓝点用一条点。为了简化，我们将每个蓝点用一条最小的紫最小的紫边边连接到红点上，构成生成树的连接到红点上，构成生成树的n n1 1条边。条边。8初态：初态：任选一个顶点作为红点，不妨设是任选一个顶点作为红点，不妨设是V1V1。邻。邻接矩阵的
15、接矩阵的V1V1行就是行就是n n1 1条连接蓝点的紫边。条连接蓝点的紫边。8从紫边集中选一条最小的紫边，将相应的蓝点从紫边集中选一条最小的紫边，将相应的蓝点VjVj变成红点。变成红点。8检测剩余蓝点到新红点检测剩余蓝点到新红点VjVj的边是否小于原来的紫的边是否小于原来的紫边。若小，则用蓝点到新红点边。若小，则用蓝点到新红点VjVj的紫边取代原来的紫边取代原来的紫边的紫边G.arcs01234506151653215564355243665426012345G.vexsV1V2V3V4V5V6Prim算法的存储结构(1)：无向网用邻接矩阵表示无向网用邻接矩阵表示AFEGDCB12101614
16、97652348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676296 14891097652348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676296 1489AFEGDCB121614Edges0123456adjvexlowcost0 12AAAAAA16 14设：初态时红点集中只有一设：初态时红点集中只有一个顶点个顶点A A；邻接矩阵的第邻接矩阵的第0 0行表示了所行表示了所有的紫边有的紫边12101614
17、97652348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676296 1489AFEGDCBEdges0123456adjvexlowcost0 12AAAAAA16 140B10B7选中最小紫边（选中最小紫边（A,B)A,B)；B B并入红点集；并入红点集；调整蓝点调整蓝点C C，F F所关联的紫所关联的紫边边12101497652348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676296 1489AFEGDC
18、Bclosedge0123456adjvexlowcost0ABAABA10 140F67选中最小紫边（选中最小紫边（B,F)B,F)；F F并入红点集；并入红点集；调整蓝点调整蓝点C,E,GC,E,G所关联的紫所关联的紫边边0F29F1297652348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676296 1489AFEGDCBclosedge0123456adjvexlowcost0AFAFBF62900选中最小紫边（选中最小紫边（F,E)F,E)；E E并入红点集；并入红点集；调整蓝点调整蓝点C,
19、D,GC,D,G所关联的紫所关联的紫边边0E5E4E812752348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676296 1489AFEGDCBEdges0123456adjvexlowcost0AEEFBE541680B0选中最小紫边（选中最小紫边（E,D)E,D)；D D并入红点集；并入红点集；调整蓝点调整蓝点C C所关联的紫边所关联的紫边0D301272348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676
20、296 1489AFEGDCBEdges0123456adjvexlowcost0AEEFBE30800选中最小紫边（选中最小紫边（D,C)D,C)；C C并入红点集；并入红点集；没有需要调整的紫边没有需要调整的紫边001272348G.vexs 0123456ABCDEFGG.arcs012345601216 141 12107210356334454285 1676296 1489AFEGDCBEdges0123456adjvexlowcost0AEEFBE0800选中最小紫边（选中最小紫边（E,G)E,G)；G G并入红点集；并入红点集；最小生成树构造完毕最小生成树构造完毕000Krus
21、kal算法：ECDCCBEFBAAAFDEEFFGGCBGF2345678910 12 14 16ABCDEFAFEGDCB127238GA B C D E,F GA B C,D E,F G4A B C,D,E,F GA B,C,D,E,F GA B,C,D,E,F,GA,B,C,D,E,F,G经典例题解析经典例题解析v【例例1 1】若无向图若无向图G=(V,E)G=(V,E)中合有中合有7 7个顶点，要保证图个顶点，要保证图G G在任在任何情况下都是连通的，则需要的边数最少是何情况下都是连通的，则需要的边数最少是vA A6 B6 B15 C15 C16 D16 D2121v【解析解析】无向图
22、中，如果每个顶点都有到其它所有顶点的路无向图中，如果每个顶点都有到其它所有顶点的路径，那么这个无向图是连通图。这个题是要保证图径，那么这个无向图是连通图。这个题是要保证图G G在任何在任何情况下都是连通的所需要的最少边数，关键是要把握情况下都是连通的所需要的最少边数，关键是要把握“在任在任何情况下都是连通的何情况下都是连通的”。在顶点固定的情况下，全连通图用。在顶点固定的情况下，全连通图用的边最多。极端情况是所有的边都被用于将部分顶点连接成的边最多。极端情况是所有的边都被用于将部分顶点连接成全连通图，而另一个部分顶点被孤立。全连通图，而另一个部分顶点被孤立。1515条边能够保证条边能够保证6
23、6个个顶点的无向图成为全连通图，所以若只有顶点的无向图成为全连通图，所以若只有1515条边，则可能出条边，则可能出现现6 6个顶点全连通而第个顶点全连通而第7 7个顶点被孤立的情况。再加上一条边个顶点被孤立的情况。再加上一条边就能保证就能保证7 7个顶点的无向图在任何情况下的连通性，所以答个顶点的无向图在任何情况下的连通性，所以答案是案是C C，最少加数是，最少加数是1616条。条。42v对下图进行拓扑排序，可以得到不同拓扑序列的个对下图进行拓扑排序，可以得到不同拓扑序列的个数是数是vA.4 B.3 C.2 D.1A.4 B.3 C.2 D.1v【解析解析】拓扑排序是指有向无环图中各顶点构成的
24、拓扑排序是指有向无环图中各顶点构成的有序序列。有序序列。v拓扑排序的步骤为：拓扑排序的步骤为：(1)(1)在有向图中选一个没有前在有向图中选一个没有前驱的顶点并且输出之；驱的顶点并且输出之；v(2)(2)从图中删除除该顶点和所以以它为尾的弧。重复从图中删除除该顶点和所以以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。的顶点可能不唯一，所以拓扑排序的结果也不唯一。根据拓扑排序的构造方法，该图中的拓扑排序有根据拓扑排序的构造方法，该图中的拓扑排序有abcedabced、aebcdaebcd、ab
25、ecdabecd三个。三个。43命题思路命题思路7 7：考察图的遍历与应用，多为综合题：考察图的遍历与应用，多为综合题v1.1.下面是用邻接表存储的图，画出此图，并写出：下面是用邻接表存储的图，画出此图，并写出：【西电西电20052005】v(1)(1)从从A A点开始根据该邻接表按深度优先遍历该图的点开始根据该邻接表按深度优先遍历该图的结果。结果。v(2)(2)从从A A点开始根据该邻接表拓扑排序该图的结果点开始根据该邻接表拓扑排序该图的结果44v解析解析v(1)(1)深度优先遍历结果：深度优先遍历结果：A-B-C-H-D-E-A-B-C-H-D-E-F-GF-Gv(2)(2)拓扑排序结果：拓扑排序结果：A B D C E G H FA B D C E G H F45