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

1、数据结构数据结构重难点串讲重难点串讲讲师：翔高教育一级培训师地点：上海第第5章章 图图重难点导航重难点导航v 图的存储结构，尤其是邻接矩阵和邻接表图的存储结构，尤其是邻接矩阵和邻接表v 图的遍历算法；广度优先搜索遍历和深度优先搜索图的遍历算法；广度优先搜索遍历和深度优先搜索遍历。图的遍历是图各种运算的基础遍历。图的遍历是图各种运算的基础v 最小生成树的生成算法以及过程，熟练掌握最小生成树的生成算法以及过程，熟练掌握prim和和kruskal算法，特别是利用两算法手工模拟生成算法，特别是利用两算法手工模拟生成树的生成过程树的生成过程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/vrty

3、pe为弧的类型。图为弧的类型。图-0,1;-0,1;网网-权值权值 infotype *info; /与弧相关的信息的指针与弧相关的信息的指针, ,可省略可省略arccell, adjmatrixmax_nmax_n;typedef struct/图的类型图的类型 vertextype vexsmax_n;/顶点向量顶点向量 adjmatrix arcs;/邻接矩阵邻接矩阵 int vexnum, arcnum;/顶点数，边数顶点数，边数 graphkind kind；/图类型图类型mgraph; v1v7v4v3v5v6v2v10v21v32v43v54v65v760123456001110

4、00100011112100000131000000401000105010010060110000g.arcs=g.vexs=无向图的邻接矩无向图的邻接矩阵阵存放顶点的数组表示边的矩阵v10v21v32v43v54v65v76v8701234567000000000100000001211010000310000000401000100501110000600010100700001010g.arcs=g.vexs=v1v7v4v3v5v6v2v8有向图的邻接矩有向图的邻接矩阵阵存放顶点的数组存放顶点的数组表示弧的矩阵表示弧的矩阵v4的出边邻接点v4的入边邻接点无无向图邻接矩阵的特点：向图邻

5、接矩阵的特点：8 对称矩阵对称矩阵8 顶点顶点vivi的度等于第的度等于第i i行非零元个数，或第行非零元个数，或第i i列非列非零元个数：零元个数：8 矩阵非零元总数等于边数的矩阵非零元总数等于边数的2 2倍倍 1010.td(vi)nknkikarcsgkiarcsg有向图邻接矩阵的特点：有向图邻接矩阵的特点：8 是非对称矩阵是非对称矩阵8 第第i i行非零元个数等于顶点行非零元个数等于顶点vivi的出度；第的出度；第i i列非列非零元个数等于顶点零元个数等于顶点vivi的入度：的入度：8 矩阵非零元总数等于边数矩阵非零元总数等于边数 10.od(vi)nkkiarcsg10.)(nkik

6、arcsgviida0b1c2d30123031512963428g.arcs=g.vexs=有向网的邻接矩阵示例：有向网的邻接矩阵示例：68314592adcb7.2.1 邻接表表示法邻接表表示法将每个顶点的邻接点串成一个单链表：将每个顶点的邻接点串成一个单链表：邻接点邻接点adjvex后继指针后继指针nextarc边信息指针边信息指针info顶点数据顶点数据data边链头指针边链头指针firstarc边结点边结点顶点结点顶点结点v1v7v4v3v5v6v2012345689datav1v2v3v4v5v6v71321546010firstarc645021g.vertices无向图的邻接表

7、：无向图的邻接表：adjvex nextarc无向图邻接表的特点：无向图邻接表的特点：8 顶点顶点vivi的度等于的度等于vivi所引导的单链表的长度所引导的单链表的长度8 边结点的个数等于边数的边结点的个数等于边数的2 2倍倍 有向图的邻接表：v1v7v4v3v5v6v2v8012345689datav1v2v3v4v5v6v7v81327654firstarcadjvex nextarc5427245g.vertices有向图邻接表的特点：8 顶点顶点vi引导的单链表是出边链，链表的长度等引导的单链表是出边链，链表的长度等于于vi的出度的出度8 找一个顶点的出边容易，找入边需要遍历整个找一

8、个顶点的出边容易，找入边需要遍历整个邻接表邻接表8 边结点的个数等于边数边结点的个数等于边数深度优先搜索遍历深度优先搜索遍历(dfs)(dfs)8depth first search;8类似于树的先根遍历类似于树的先根遍历; ;8优先向纵深访问优先向纵深访问dfsdfs遍历过程：遍历过程：1. 从图从图g中选某个顶点中选某个顶点v作为出发点；作为出发点；2. 访问访问v；3. 依次从依次从v的未被访问的邻接点出发，深度优先搜的未被访问的邻接点出发，深度优先搜索遍历图索遍历图g, 直至与直至与v相通的顶点都被访问完；相通的顶点都被访问完；4. 如果此时图如果此时图g中还有顶点未曾被访问，则从这些

9、中还有顶点未曾被访问，则从这些未被访问的顶点中再选一个顶点未被访问的顶点中再选一个顶点v，转，转2，继续，继续遍历；否则遍历结束遍历；否则遍历结束。v1v7v4v3v5v6v2出发点dfs访问序列：v1v2v5v6v7v3v4v1出发点出发点dfsdfs访问序列：访问序列：v3v2v4v9v1v6v5v2v4v3v6v5v8v7v9v8v7v8v3v1v7v4v9v5v6v2出发点出发点dfs访问序列：访问序列：v1v9v7v2v5v6v4data87v76v65v54v43v92v21v108311546012firstarc054681v8v370v3v8v1v7v4v3v5v6v2v8d

10、ata8v87v76v65v54v43v32v21v101327654firstarc2457256g.verticesdfs访问序列：访问序列：v1v2v3v6v5v8v7v4出发点出发点bfs遍历过程：遍历过程：1.1. 从图从图g g的某个顶点的某个顶点v v出发，访问出发，访问v v；2.2.依次依次访问访问v v的未被访问的邻接点；的未被访问的邻接点；3.3. 再按照再按照“先被访问顶点的邻接点先访问先被访问顶点的邻接点先访问”的次序，依的次序，依次访问这些邻接点的邻接点，直至图中所有已被次访问这些邻接点的邻接点，直至图中所有已被访问的顶点的邻接点都被访问到；访问的顶点的邻接点都被访

11、问到；4.4. 若此时图中还有顶点未曾被访问，则另选一个未若此时图中还有顶点未曾被访问，则另选一个未被访问的顶点被访问的顶点v v作为出发点，重复上述过程，直至作为出发点，重复上述过程，直至图中所有的顶点都被访问完。图中所有的顶点都被访问完。v1出发点出发点bfsbfs访问序列：访问序列：v3v2v1v6v4v5v9v2v4v3v6v5v8v7v9v8v7v1v7v4v3v5v6v2v8访问序列：访问序列：v1v2v4v5v6v7v8出发点v3data8v87v76v65v54v43v32v21v101327654firstarc2457256求无向图的连通分量：求无向图的连通分量： 对无向图

12、对无向图g调用一次调用一次dfs过程，能访问完过程，能访问完g的的一个连通分量。因此对一个连通分量。因此对dfs算法稍做修改就可解决算法稍做修改就可解决求无向图连通分量的问题求无向图连通分量的问题。最小生成树最小生成树8 最小最小(代价代价)生成树：生成树：无向网的所有生成树中，无向网的所有生成树中，边权之和最小的生成树。边权之和最小的生成树。8 构造最小生成树的著名算法：构造最小生成树的著名算法： prim算法算法 kruskal算法算法8 在在n个城市之间建通讯网；个城市之间建通讯网；8 可能的线路最多有可能的线路最多有n(n-1)/2条；条；8 从中选择从中选择n1条，满足：条，满足：(

13、1)连通；连通；(2)边上权值之和为最小。边上权值之和为最小。8 这就是构造这就是构造最小代价生成树最小代价生成树。v1v2v4v5v6v35613266554最小生成树的最小生成树的mstmst性质性质： 设设g(v, e)是一个连通网，是一个连通网，u是顶点是顶点v的一个非空的一个非空子集。若子集。若(u, v)是一条具有是一条具有最小权值的边最小权值的边，且，且uu集，集，vvu集，则必存在一棵包含边集，则必存在一棵包含边(u, v)的最小生成树。的最小生成树。v1v2v4v5v6v35613266554u集(红点集)vu集(蓝点集)联接红点和蓝点的边(紫边)最小紫边一定会最小紫边一定会

14、在在g g的某棵最小的某棵最小生成树上出现生成树上出现primprim算法思想：算法思想：8 由于红点集与蓝点集的划分是任意的，经过由于红点集与蓝点集的划分是任意的，经过n n1 1次不同的划分，找到每次划分的最小紫边，以此次不同的划分，找到每次划分的最小紫边，以此来构成最小生成树的来构成最小生成树的n-1n-1条边。条边。8 在每次划分中，每个蓝点可能有多条紫边连接红在每次划分中，每个蓝点可能有多条紫边连接红点。为了简化，我们将每个蓝点用一条点。为了简化，我们将每个蓝点用一条最小的紫最小的紫边边连接到红点上，构成生成树的连接到红点上，构成生成树的n n1 1条边。条边。8 初态：初态：任选一

15、个顶点作为红点，不妨设是任选一个顶点作为红点，不妨设是v1v1。邻。邻接矩阵的接矩阵的v1v1行就是行就是n n1 1条连接蓝点的紫边。条连接蓝点的紫边。8 从紫边集中选一条最小的紫边，将相应的蓝点从紫边集中选一条最小的紫边，将相应的蓝点vjvj变成红点。变成红点。8 检测剩余蓝点到新红点检测剩余蓝点到新红点vjvj的边是否小于原来的紫的边是否小于原来的紫边。若小，则用蓝点到新红点边。若小，则用蓝点到新红点vjvj的紫边取代原来的紫边取代原来的紫边的紫边g.arcs01234506151653215564355243665426g.vexs0v11v22v33v44v55v6prim算法的存储

16、结构(1)：无向网用邻接矩阵表示无向网用邻接矩阵表示afegdcb1210161497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g614891210161497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost01234561097652348g.vexsg.arcs01234560a01216141b1121072c2103563d334

17、4e454285f51676296g61489afegdcb121614edgesadjvexlowcost0012345612aaaaaa16 14设：初态时红点集中只有设：初态时红点集中只有一个顶点一个顶点a a；邻接矩阵的第邻接矩阵的第0 0行表示了所行表示了所有的紫边有的紫边1210161497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost0012345612aaaaaa16 140b10b7选中最小紫边（选中最小紫边（a,b)

18、a,b)；b b并入红点集；并入红点集；调整蓝点调整蓝点c c，f f所关联的紫所关联的紫边边12101497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbclosedgeadjvexlowcost00123456abaaba10 140f67选中最小紫边（选中最小紫边（b,f)b,f)；f f并入红点集；并入红点集；调整蓝点调整蓝点c,e,gc,e,g所关联的紫所关联的紫边边0f29f1297652348g.vexsg.arcs01234560a01216141b112

19、1072c2103563d3344e454285f51676296g61489afegdcbclosedgeadjvexlowcost00123456afafbf62900选中最小紫边（选中最小紫边（f,e)f,e)；e e并入红点集；并入红点集；调整蓝点调整蓝点c,d,gc,d,g所关联的紫所关联的紫边边0e5e4e812752348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost00123456aeefbe541680b0选中最小紫边（选中最小紫

20、边（e,d)e,d)；d d并入红点集；并入红点集；调整蓝点调整蓝点c c所关联的紫边所关联的紫边0d301272348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost00123456aeefbe30800选中最小紫边（选中最小紫边（d,c)d,c)；c c并入红点集；并入红点集；没有需要调整的紫边没有需要调整的紫边001272348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f5

21、1676296g61489afegdcbedgesadjvexlowcost00123456aeefbe0800选中最小紫边（选中最小紫边（e,g)e,g)；g g并入红点集；并入红点集；最小生成树构造完毕最小生成树构造完毕000kruskal算法：ecdccbefbaaafdeeffggcbgf2345678910 12 14 16a b c d e fafegdcb127238ga 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经典例题解析经

22、典例题解析v 【例【例1】若无向图】若无向图g=(v,e)中合有中合有7个顶点，要保证图个顶点，要保证图g在在任何情况下都是连通的，则需要的边数最少是任何情况下都是连通的，则需要的边数最少是v a6 b15 c16 d21v 【解析】无向图中，如果每个顶点都有到其它所有顶点的路【解析】无向图中，如果每个顶点都有到其它所有顶点的路径，那么这个无向图是连通图。这个题是要保证图径，那么这个无向图是连通图。这个题是要保证图g在任何在任何情况下都是连通的所需要的最少边数，关键是要把握情况下都是连通的所需要的最少边数，关键是要把握“在任在任何情况下都是连通的何情况下都是连通的”。在顶点固定的情况下，全连通图用。在顶点固定的情况下，全连通图用的边最多。极端情况是所有的边都被用于将部分顶点连接成的边最多。极端情况是所有的边都被用于将部分顶点连接成全连通图，而另一个部分顶点被孤立。全连通图，而另一个部分顶点被孤立。15条边能够保证条边能够保证6个个顶点的无向图成为全连通图，所以若只有顶点的无向图成为全连通图，所以若只有15条边，则可能条边，则可能出现出现6个顶点全连通而第个顶点全连通而第7个顶点被孤立的情况。再加上一个顶点被孤立的情况。再加