图结构习题答案

n个顶点的强连通图至少有多少条边?这样的图应该就是什么形状?这就是一个与生成树相关的问题。生成树就是一个连通图,它具有能够连通图中任何两个顶点的最小边集,任何一个生成树都具有n-1边。因此,具有n个顶点的连通图至少有n-1连通,因此每个顶点至少要有一条以该顶点为弧头的弧与一条以该顶点为弧尾的弧,每个顶点可得:边数=2×n/2=n。这就是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列,不妨设这n个顶点排成的拓扑序列为v1,v2,v3,…,vn,那么在这个序列中,每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧,最多有n-i条,因此在整个图中最多有(n-1)+(n-2)+…2.图的存储结构常用的存储结构有邻接矩阵与邻接表。(1)邻接矩阵表示法11当(Vi,Vj)∈E或<Vi,Vj>∈E时costij0其它AA000100A由邻接矩阵的定义可知,无向图的邻接矩阵必定就是对称阵;有向图的邻接矩阵不一定就根据邻接矩阵,很容易判定任意两个顶点之间就是否有边相连。求各顶点的度也就是非常容易的。对于无向图,顶点Vi的度就就是邻接矩阵中第i行(或第j列)上非零元的个数,即ii=1。对于有向图,第i行中非零元的个数为顶点Vi的出度,而第i列上的非零(2)邻接表表示法图的邻接链表存储结构就是一种顺序分配与链式分配相结合的存储结构括两个部分:一部分就是向量,另一部分就是链表。在无向图的邻接表中顶点vi的度就就是第i个链表中结点的个数。在有向图中,第i个123∧33∧1123434432322∧∧G对于这类问题,只要掌握了图的概念与存储结构就可以做出正确的答案。通常情况下.对图的顶点排列顺序与各顶点的邻接点排列顺序并没有特定要求,因此,在写出邻接矩阵与邻接表表示时,只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的就是,对于邻接矩阵表示,如果顶点结点的顺序不同,那么邻接矩阵就不相同;对于邻接表表示,如果顶点结点的顺序或者邻接点的顺序不同,那么邻接表就不相同。25143600000010100000000000000011101123456∧∧∧∧4∧∧256644(1)画出该无向图;(2)根据邻接表,分别写出用DFS(深度优先搜索)与BFS(广度优先搜索)算法从顶点V0开始遍历该图后所得到的遍历序列。11∧∧∧6464∧∧V0V1V2V3V4V5V650323523002v0v1接表表示,从顶点V0开始的深度优先遍历序列为:V0、V2、V3、从图的逻辑结构上来讲,从图中某个顶点开始的深度(或广度)优先遍历序列不一定就是唯一的。这就是因为在逻辑结构中,并没有对每个顶点的所有邻接点规定它们之间的先后顺序,这样在搜索算法中选取第—个邻接点与下一个邻接点时可能会有不同的结果。但就是在存储结构中,明确地给出了邻接点的先后顺序,这时深度优先与广度优先遍历序列就就是唯一(1)利用Prim算法从顶点a开始构造最小生成树的过程;(2)利用Kruskal算法构造最小生成树的过程;991g8c849f6be5dffbbbbcbcadadadffbbbbcbcadadaaaaeeggeffddgga2efd1gccabb32f1gdccabb3244f1gdcc3de4fgf6baad2efg61bcddeeggccffe1ccefgf1b2f2f1g1b3d2ef1bc3d24e4fgf1bcdd1g32efab4【例6-5】一个带权无向图的最小生成树就是否一定唯一？在什么情况下构造出的最小生过程可以瞧出,当从图中选择当前权值最小的边时,如果存在多条这样的边,并且这些边与已经选取的边构成回路,此时这些边就不可能同时出现在一棵最小生成树中,对这些边的不同选择结果可能会产生不同的最小生成树。一、单项选择题3、在一个具有n个顶点的无向图中,若具有e条边,则所有顶点的度数之与为(3、D)。6、在一个无向图中,若两顶点之间的路径长度为k,则该路径上的顶点数为(6、eke二、填空题11、在有向图的邻接表与逆邻接表表示中,每个顶点邻接表分别链接着该顶点的所有到的顶点序列为____________,从顶点a出发进行广度优先搜索遍历得到的顶点序列为a17、对于一个具有n个顶点与e条边的连通图,其生成树中的顶点数与边数分别为d三、应用题优先搜索遍历得到的顶点序列与按广度优先搜索遍历得到的顶点序列。注:每一种序列都就是唯一的,因为都就是在存储结构上得到的。点就是按出边邻接点序号从大到小的次序链接的,试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列与按广度优先搜索遍历得到的顶点序列。注:每一种序列都就是唯一的,因为都就是在存储结构上得到的。0046598200468优先与广度优先搜索遍历得到的顶点序列。b优先与广度优先搜索遍历得到的顶点序列。V3V4V3V4V2V6a(b):0,3,2,6,5,4,1V1V3V7V7V2V2V4V5V6VV2VV1VV4VV5VV3VV6VV7V2V1V4VV5VV3VV6VV7V2V1V1V1VV7V5V5V2V1V3V4V7V5V6V4VV3VV6V2VV7V1V4V5V2V3V6V1V4V5(f)V7V3V6VV7V3VV3V7V1V1V3V2V26542V4V7V5V6VV1VV2V5V1V2V5VV3V4V7V6V3V4V7V6VV1V2V4V5V6VV1V2V4V5V3V7V6VV3V2V4V2V5V6V2V1V3V4V5V6V7(f)V5V56030V4VV4∞∞∞∞∞∞∞∞∞∞∞∞5∞∞∞20∞50∞∞V1∞10∞20∞60V3∞∞∞∞V2(a)(a)有向带权图∞无∞∞{v0,v2}VjS∞∞∞minvlvlvl(5)=min{vl(7)-8,vl(8)-4}=7vl(3)=min{vl(5)-3,vl(6)-5}=4vlvl(1)=min{vl(2)-3,vl(3)-4}=0四、算法设计题{//根据无向图的邻接矩阵求出序号为numb的顶点的度数}//根据有向图的邻接矩阵求出序号为numb的顶点的度数{inti,j,d=0;//求出顶点numb的出度NT//求出顶点num