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

数据结构重难点串讲讲师：翔高教育一级培训师地点：上海第5章图重难点导航图的存储结构，尤其是邻接矩阵和邻接表图的遍历算法；广度优先搜索遍历和深度优先搜索遍历。图的遍历是图各种运算的基础最小生成树的生成算法以及过程，熟练掌握Prim和Kruskal算法，特别是利用两算法手工模拟生成树的生成过程图的应用：最小生成树，拓扑排序，关键路径，最短路径3邻接矩阵表示法(数组表示法)用一个一维数组存放图的顶点数据用一个矩阵A[n][n]来存放图的边的信息:有向/无向图:A[i][j]＝0反之1若Vi,Vj或(Vi,Vj)E(G)有向/无向网:A[i][j]＝∞或0反之wij若Vi,Vj或(Vi,Vj)E(G)图的邻接矩阵定义：typedefstruct{//弧结点与矩阵的类型VRTypeadj;//VRType为弧的类型。图--0,1;网--权值InfoType*Info;//与弧相关的信息的指针,可省略}ArcCell,AdjMatrix[max_n][max_n];typedefstruct{//图的类型VertexTypevexs[max_n];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//顶点数，边数GraphKindkind；//图类型}MGraph;V1V7V4V3V5V6V2V1V2V3V4V5V6V70123456012345600111000110001112100000131000000401000105010010060110000G.arcs=G.vexs=无向图的邻接矩阵存放顶点的数组表示边的矩阵V1V2V3V4V5V6V7V80123456701234567001110000100101100200000100300100110400000001500001010600000001700000000G.arcs=G.vexs=V1V7V4V3V5V6V2V8有向图的邻接矩阵存放顶点的数组表示弧的矩阵V4的出边邻接点V4的入边邻接点无向图邻接矩阵的特点：对称矩阵顶点Vi的度等于第i行非零元个数，或第i列非零元个数：矩阵非零元总数等于边数的2倍1010]][[.]][[.TD(Vi)nknkikarcsGkiarcsG有向图邻接矩阵的特点：是非对称矩阵第i行非零元个数等于顶点Vi的出度；第i列非零元个数等于顶点Vi的入度：矩阵非零元总数等于边数10]][[.OD(Vi)nkkiarcsG10]][[.)(nkikarcsGViIDABCD012301230∞1∞41∞∞92235∞83∞∞6∞G.arcs=G.vexs=有向网的邻接矩阵示例：68314592ADCB7.2.1邻接表表示法将每个顶点的邻接点串成一个单链表：邻接点后继指针边信息指针顶点数据边链头指针adjvexnextarcinfodatafirstarc边结点顶点结点V1V7V4V3V5V6V2data0V11V22V33V44V55V66V7891∧321∧5∧4∧601∧0firstarc645∧0∧21G.vertices无向图的邻接表：adjvexnextarc无向图邻接表的特点：顶点Vi的度等于Vi所引导的单链表的长度边结点的个数等于边数的2倍有向图的邻接表：V1V7V4V3V5V6V2V8data0V11V22V33V44V55V66V78V8∧91∧32∧7∧6∧54firstarcadjvexnextarc54∧2∧724∧5G.vertices有向图邻接表的特点：顶点Vi引导的单链表是出边链，链表的长度等于Vi的出度找一个顶点的出边容易，找入边需要遍历整个邻接表边结点的个数等于边数深度优先搜索遍历(DFS)DepthFirstSearch;类似于树的先根遍历;优先向纵深访问DFS遍历过程：1.从图G中选某个顶点V作为出发点；2.访问V；3.依次从V的未被访问的邻接点出发，深度优先搜索遍历图G,直至与V相通的顶点都被访问完；4.如果此时图G中还有顶点未曾被访问，则从这些未被访问的顶点中再选一个顶点V，转2，继续遍历；否则遍历结束。V1V7V4V3V5V6V2出发点DFS访问序列：V1V2V5V6V7V3V4V1DFS访问序列：V3V2V4V9V1V6V5V2V4V3V6V5V8V7V9V8V7V8V3V1V7V4V9V5V6V2出发点DFS访问序列：V1V9V7V2V5V6V4data87V76V65V54V43V92V21V108∧311∧5∧4∧601∧2firstarc054∧6∧81V8V3∧7∧0V3V8V1V7V4V3V5V6V2V8data8∧V87V76V65V54V43V32V21V101∧32∧7∧6∧54firstarc24∧5∧725∧6G.verticesDFS访问序列：V1V2V3V6V5V8V7V4出发点BFS遍历过程：1.从图G的某个顶点v出发，访问v；2.依次访问V的未被访问的邻接点；3.再按照“先被访问顶点的邻接点先访问”的次序，依次访问这些邻接点的邻接点，直至图中所有已被访问的顶点的邻接点都被访问到；4.若此时图中还有顶点未曾被访问，则另选一个未被访问的顶点v作为出发点，重复上述过程，直至图中所有的顶点都被访问完。V1BFS访问序列：V3V2V1V6V4V5V9V2V4V3V6V5V8V7V9V8V7V1V7V4V3V5V6V2V8访问序列：V1V2V4V5V6V7V8出发点V3data8∧V87V76V65V54V43V32V21V101∧32∧7∧6∧54firstarc24∧5∧725∧6求无向图的连通分量：对无向图G调用一次DFS过程，能访问完G的一个连通分量。因此对DFS算法稍做修改就可解决求无向图连通分量的问题。最小生成树最小(代价)生成树：无向网的所有生成树中，边权之和最小的生成树。构造最小生成树的著名算法：Prim算法Kruskal算法在n个城市之间建通讯网；可能的线路最多有n(n-1)/2条；从中选择n－1条，满足：(1)连通；(2)边上权值之和为最小。这就是构造最小代价生成树。V1V2V4V5V6V35613266554最小生成树的MST性质：设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，且u∈U集，v∈V－U集，则必存在一棵包含边(u,v)的最小生成树。V1V2V4V5V6V35613266554U集(红点集)V－U集(蓝点集)最小紫边一定会在G的某棵最小生成树上出现Prim算法思想：由于红点集与蓝点集的划分是任意的，经过n－1次不同的划分，找到每次划分的最小紫边，以此来构成最小生成树的n-1条边。在每次划分中，每个蓝点可能有多条紫边连接红点。为了简化，我们将每个蓝点用一条最小的紫边连接到红点上，构成生成树的n－1条边。初态：任选一个顶点作为红点，不妨设是V1。邻接矩阵的V1行就是n－1条连接蓝点的紫边。从紫边集中选一条最小的紫边，将相应的蓝点Vj变成红点。检测剩余蓝点到新红点Vj的边是否小于原来的紫边。若小，则用蓝点到新红点Vj的紫边取代原来的紫边G.arcs0123450∞615∞∞16∞5∞3∞215∞56435∞5∞∞24∞36∞∞65∞∞426∞012345G.vexsV1V2V3V4V5V6Prim算法的存储结构(1)：无向网用邻接矩阵表示AFEGDCB1210161497652348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞1097652348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞AFEGDCB121614∞∞∞Edges0123456adjvexlowcost012AAAAAA∞∞∞1614设：初态时红点集中只有一个顶点A；邻接矩阵的第0行表示了所有的紫边1210161497652348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞AFEGDCB∞∞∞Edges0123456adjvexlowcost012AAAAAA∞∞∞16140B10B7选中最小紫边（A,B)；B并入红点集；调整蓝点C，F所关联的紫边12101497652348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞AFEGDCB∞∞closedge0123456adjvexlowcost0ABAABA10∞∞140F67选中最小紫边（B,F)；F并入红点集；调整蓝点C,E,G所关联的紫边0F29F1297652348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞AFEGDCB∞closedge0123456adjvexlowcost0AFAFBF6∞2900选中最小紫边（F,E)；E并入红点集；调整蓝点C,D,G所关联的紫边0E5E4E812752348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞AFEGDCBEdges0123456adjvexlowcost0AEEFBE541680B0选中最小紫边（E,D)；D并入红点集；调整蓝点C所关联的紫边0D301272348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞AFEGDCBEdges0123456adjvexlowcost0AEEFBE30800选中最小紫边（D,C)；C并入红点集；没有需要调整的紫边001272348G.vexs0123456ABCDEFGG.arcs01234560∞12∞∞∞1614112∞10∞∞7∞2∞10∞356∞3∞∞3∞4∞∞4∞∞54∞2851676∞2∞9614∞∞∞89∞AFEGDCBEdges0123456adjvexlowcost0AEEFBE0800选中最小紫边（E,G)；G并入红点集；最小生成树构造完毕000Kruskal算法：ECDCCBEFBAAAFDEEFFGGCBGF2345678910121416{A}{B}{C}{D}{E}{F}AFEGDCB127238{G}{A}{B}{C}{D}{E,F}{G}{A}{B}{C,D}{E,F}{G}4{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在任何情况下都是连通的，则需要的边数最少是A．6B．15C．16D．21【解析】无向图中，如果每个顶点都有到其它所有顶点的路径，那么这个无向图是连通图。这个题是要保证图G在任何情况下都是连通的所需要的最少边数，关键是要把握“在任何情况下都是连通的”。在顶点固定的情况下，全连通图用的边最多。极端情况是所有的边都被用于将部分顶点连接成全连通图，而另一个部分顶点被孤立。15条边能够保证6个顶点的无向图