数据结构（Java语言版）-习题及答案 第8章图习题答案

第8章图习题参考答案 一、单选题ABCABCD./2124ABCABCDnn(n-1)C.nn/2.nABCABCDnn(n-1)C.nn/2.nABCABCDnn+ln-1n/2ABCABCDnn+ln-1n/2ABCABCD完全图连通图非连通图以上都不对ABCABCD01n-1nABCABCD01n-1nABCABCD无向图有向图无向图或有向图以上都不对ABC一个图的邻接矩阵不是对称矩阵，则该图可能是ABC无向图有向图无向图或有向图D以上都不对DABCABCD有向图无向图无向图或有向图以上都不对ABCABCDn.n2C.n1.n2ABCABCDn2ne2eABCABCD与图的顶点和边数有关只与图的边数有关只与图的顶点数有关与边数的平方有关ABCABCD顶点v的度顶点v的出度顶点v的入度ABCABCD顶点v的度顶点v的出度顶点v的入度ABCABCD完全图连通图有回路一棵树ABCABCD图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次图的深度优先遍历适合无向图图的深度优先遍历不适合有向图图的深度优先遍历是一个递归过程无向图=，E，其中=，b，c，d，e，，E=，b，，e，，c，b，e，c，，，d，e，d，下面对该图进行深度优先遍历得到的顶点序列正确的是 。Aa，b，e，c，d，fA

B.Ba，c，f，e，b，dCDC.，e，b，c，，CD.，e，d，，c，bABCABCDnn-1n+1不确定设有无向图=，E和G=，;，如是的生成树，则以下不正确的说法是 。AABCD为的连通分量是的无环子图为的子图为的极小连通子图且=VABCABCD由n-1条权值最小的边构成的子图由n条权值之和最小的边构成的子图由n个顶点构成的极大连通子图由n个顶点构成的极小连通子图，且边的权值之和最小用r算法求一个连通的带权图的最小生成树，在算法执行的某时刻，已选取的顶点集合＝，，，已选取的边的集合E＝，，(2，3)}，要选取下一条权值最小的边，应当从 组边中选取。ABCD.，，，，，，ABCD.，，，，，}C.，，，，，}.，，，，，，，}用r算法求一个连通的带权图的最小生成树，在算法执行的某时刻，已选取的顶点集合＝，，，边的集合E＝，，(2，3)}，要选取下一条权值最小的边，不可能从 组中选取。ABCD.，，，，，，ABCD.，，，，，}C.，，，，，}.，，，，，，，}

用ruk算法求一个连通的带权图的最小生成树，在算法执行的某时刻，已选取的边集合E＝，，，，，，要选取下一条权值最小的边，不可能选取的边是 。AABCD.，).，)C.，).，)对某个带权连通图构造最小生成树，以下说法中正确的是 。Ⅰ该图的所有最小生成树的总代价一定是唯一的Ⅱ其所有权值最小的边一会出现在所有的最小生成树中Ⅲ用普里姆（r）算法从不同顶点开始构造的所有最小生成树一定相同Ⅳ使用普里姆算法和克鲁斯卡尔（ruk）算法得到的最小生成树总不相同AABCD仅Ⅰ仅Ⅱ仅Ⅰ、ⅢⅡ、ⅣABn个顶点e条边的带权有向图采用邻接矩阵存储，求最短路径的kr算法的时间复杂度为 。ABCDOn).On+eCDC.On).One)ABCDkrABCD按长度递减的顺序按长度递增的顺序通过深度优先遍历通过广度优先遍历用kr算法求一个带权有向图中从顶点出发的最短路径，在算法执行的某时刻，S=，，，，下一步选取的目标顶点可能是 。AABCD顶点2顶点3顶点4用kr算法求一个带权有向图中从顶点出发的最短路径，在算法执行的某时刻，S=，，，，则以后可能修改最短路径是 。AABCD从顶点0到顶点2的最短路径从顶点0到顶点3的最短路径从顶点0到顶点4的最短路径的最短路径有一个顶点编号为～的带权有向图，现用Fyd算法求任意两个顶点之间的最短路径，在算法执行的某时刻，已考虑了～的顶点，现虑顶点3，则以下叙述中正确的是 。AABCD只可能修改从顶点0～2到顶点3的最短路径只可能修改从顶点3到顶点0～2的最短路径只可能修改从顶点0～2到顶点4的最短路径所有其他两个顶点之间的路径都可能被修改ABCD在有向图G的拓扑序列中，若顶点i在顶点ABCD中有边<，>G中有一条从顶点i到顶点j的路径中没有边<，>G中有一条从顶点j到顶点i的路径ABCABCD存在，且唯一存在、且不唯一存在，可能不唯一无法确定是否存在ABCABCD是个有根有向图是个强连通图含有多个入度为0的顶点含有顶点数目大于1的强连通分量以下关于图拓扑排序的叙述中正确的是 。Ⅰ任何无环的有向图，其顶点都可以排在一个拓扑序列中。Ⅱ若n个顶点的有向图有唯一的扑序列，则其边数必为n-1。Ⅲ.在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条边<a，b>AABCD仅Ⅰ仅Ⅰ、Ⅲ仅Ⅱ、Ⅲ.Ⅰ、Ⅱ和ⅢABCABCD一个拓扑序列无序的逆拓扑序列按顶点编号次序ABCABCD从源点到汇点的最长路径从源点到汇点的最短路径最长的回路最短的回路ABCD示工程的ABCD必须是唯一的可以有多条可以没有以上都不对ABCD于ABCD在AOE网中可能存在多条关键路径关键活动不按期完成就会影响整个工程的完成时间任何一个关键活动提前完成，整个工程也将提前完成所有关键活动都提前完成，整个工程也将提前完成ABCABCD访问图的所有顶点以某种次序访问图的所有顶点从一个顶点出发访问图中所有顶点且每个顶点只能访问一次从一个顶点出发访问图中所有顶点但每个顶点可以访问多次ABCABCD图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次图的深度优先遍历适合无向图图的深度优先遍历不适合有向图图的深度优先遍历是一个递归过程ABC以下（ABC遍历拓扑排序Dkr法DrABCABCD完全图连通图有回路一棵树ABCD采用邻接表存储的图的深度优先遍历算法类似于二叉树的ABCD先序遍历中序遍历后序遍历层次遍历ABCABCD1个2个任意多个0个ABCABCD./2124ABCABCDnn(n-1)C.nn/2.nABCABCDnn(n-1)C.nn/2.nABCABCDnn+ln-1n/2ABCABCD极小连通子图极小子图极大连通子图极大子图ABCABCDenn-e1ABCABCDn-1nn+12nABCABCDnn-1n+1不确定二、多选题ABCD在用r和ruk算法构造最小生成树时，前者更适合于①，后者更适合于ABCD有向图无向图稀疏图稠密图三、编程题OJ—求最长路径长度问题时间限制：，空间限制：。问题描述：在听说美国肥胖流行之后，农夫约翰希望他的奶牛能够做更多运动，因此他为他的奶牛提交了马拉松申请，马拉松路线包括一序列农场对和它们之间的道路组成的路径。由于约翰希望奶牛尽可能多地运动，他想在地图上找到彼此距离最远的两个农场（距离是根据两个农场之间的道路上的道路总长度来衡量的）。请你帮助他确定这对最远的农场之间的距离。输入格式：行1：两个以空格分隔的整数：n和m。行+行：每行包含四个空格分隔的元素，x，y，和d描述一条道路，其中x和y是一条长度为的道路相连的两个农场的编号，d是一个字符N、E、S或，表示从x到y的道路方向。输出格式：给出最远的一对农场之间距离的整数。答：prtvng*;prtvu*;prtvuScnner;csENde //边数组元素类{ntv; //邻接点nt; //边权值ntnex; //下一条边ENdentvnt) //构造方{h=;}}pubccsn{cnt=;cnt;cn]ved=newn;cn]d=newn;//存放路径长度cntn; //存放结果cntn; //cnhed=newn;cENde]edge=newENde*;cvdddEdgentuntvnt)//无向图添加<uv>和<vu>{edge=newENdev;//添加边<uv>edgenex=hedu;hedu=++;edge=newENdeu;//添加边<vu>edgenex=hedv;hedv=++;}cntFSntx) //从顶点x出发广度优先遍历{rryved;rryd;Queue<neger>qu=newnked<neger>;vedx=;qu.offer(x);ntp=;hequEpy){ntu=qup;fdu>n) //求距离顶点x最大距离的顶点p{p=u;}rnte=hedu;e=;e=edgeenex){ntnt=edgee;fvedv==){vedv=;dv=du+;qu.offer(v);}}}p;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntxy;Srngd;rryhed;=;n=nnexIn;=nnexIn;rnt=;i<=;++){x=nnexIn;y=nnexIn;=nnexIn;d=nnex;ddEdgexy;}n=;ntn=;FSp; //从顶点pSyeuprnnn;}}.HDU4514—：6000ms，空间限制：65535K。问题描述：随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？其中，可以兴建的路线均是双向的，它们之间的长度均大于0n和m，其含义参见题目描述，接下去m行，每行3个数字u、v和，分别代表这条线路的起点、终点和长度。有n≤，≤，≤u，v≤n，≤。输出格式：对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。答：prtvng*;prtvu*;prtvuScnner;csENde //边数组元素类{ntv; //邻接点nt; //边权值ntnex; //下一条边ENdentvnt) //构造方{hv=hw=;}}pubccsn{cnt=;cntE=;cnt;cnher=newn;//并查集存储结构cnrnk=newn;//秩cntn;cnthed=newn;cENdeedge=newENdeE;cvdIn //初始化{rnt=;i<=n;++)her=;rryrnk;=;rryhed;}cntFndntx) //并查集查找{fherx==x)returnx;herx=Fndherx;returnfather[x];}cvdnnntrntrb)//并查集合并{frnkr>rnkrb)herrb=r;ee{frnkr==rnkrb)rnkrb++;herr=rb;}}cntved=newn;cntx=ver;cntrecrd=newn;cvdFSntu,ntd)//FS遍历{vedu=;recrdu=;fx<d){ver=u;x=d;}rnte=hedu;e=;e=edgeenex){ntv=edgeev;fvedv==)FSvd+edgee;}}cvdddEdgentuntvnt)//无向图添加<uv>和<vu>{edge=newENdev,;edgenex=hedu;hedu=++;edge=newENdeu,;edgenex=hedv;hedv=++;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;henhNex){n=nnexIn;=nnexIn;ntrrbuv;benrk=e;nt;In;r=;i<=;++){u=nnexIn;v=nnexIn;=nnexIn;r=Fndu;rb=Fndv;fr==rb) //存在回路{rk=rue;break;}nnrrb;//合并ddEdgeuv;//}r=+;i<=;++)//中途确定有回路后还需获取其他边{u=nnexIn;v=nnexIn;=nnexIn;}frk) //有回路的情况Syeuprnn"ES";ee //没有回路的情况{rryrecrd;ntn=; //存放结果r=;i<=n;++)//从每个顶点出发搜索{frecrd==)//不搜索重复的顶点cnnue;rryved;x=;FS;//查找顶点的最远顶点vertrryved;x=;FSver;//查找顶点ver的最远顶点n=hxnx;}Syeuprnnn;}}}}OJ—高速公路问题时间限制：，空间限制：。问题描述：某岛国完全平坦，不幸的是高速公路系统非常糟糕，当地政府意识到了这个问题，并且已经建造了连接一些最重要城镇的高速公路。但是，仍有一些城镇无法通过高速公路抵达，所以有必要建造更多的高速公路让任何两个城镇之间通过高速公路连接。所有城镇的编号从到n，城镇的位置由笛卡尔坐标（x，y）给出。每条高速公路连接两个城镇。所有高速公路都直线相连，因此它们的长度等于城镇之间的笛卡尔距离。所有高速公路都是双向的。高速公路可以自由地相互交叉，但司机只能在连接高速公路的两个城镇进行切换。政府希望最大限度地降低建设新高速公路的成本。但希望保证每个城镇都能够到达。由于地势平坦，高速公路的成本总是与其长度成正比。因此，最便宜的高速公路系统将是最小化总公路长度的系统。输入格式：输入包括两部分。第一部分描述了该国的所有城镇，第二部分描述了所有已建成的高速公路。输入文件的第一行包含一个整数n（≤n≤）表示城镇数量。接下来的n行每行包含两个整数x和y，由空格分隔，给出了第个城镇的坐标（从到n）。坐标的绝对值不超过，每个城镇都有一个独特的位置。下一行包含单个整数（≤≤），表示现有高速公路的数量。接下来的m行每行包含一对由空格分隔的整数，这两个整数给出了一对已经通有高速公路的城镇编号，每对城镇至多由一条高速公路连接。输出格式：输出所有要新建的高速公路，每条输出一行，以便连接所有城镇，尽可能减少新建高速公路的总长度。如果不需要新建高速公路（所有城镇都已连接），则输出为空。答：prtvng*;prtvu*;prtvuScnner;pubccsn{cnlntINF=x;//表示∞cntn;cn]x; //城镇的x坐标cn]y; //城镇的y坐标cn]; //邻接矩阵cvdrntv) //r算{n]c=newnn;n]ce=newnn;rnt=;i<n;++)c=v;cv=; //将顶点v添加到中rnt=;i<n;++) //取n个顶点到{ntn=INFk=;rnt=;j<n;++){c=&c]<n){n=c;k=;}}n=) //输出一条边Syeuprnncek++""+k+;ck=; //将顶点k添加到中rnt=;j<n;++){c=1&k]<c){c=k;ce=k;}}}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;n=nnexIn;x=newnn;y=newnn;=newnnn;rnt=;i<n;++) //输入n个城镇{x=nnexIn;y=nnexIn;}rnt=;i<n;++) //rnt=;j<n;++){ntd=xx*xx+yy*yy;==d;}=nnexIn; //输入rnt=;i<;++){ntx=nnexIn;nty=nnexIn;xy=yx=;//将路径长度置为0}r; //从顶点出发构造最小生成树}}.OJ—重型运输问题时间限制：，空间限制：。问题描述：Hug很高兴，在Crger项目失败后他现在可以扩展业务了。但他需要一个聪明的人告诉他，能不能将货物运输到指定的客户并且满足经过的道路的最大承载量。幸运的是，他已经有了城市中所有街道和桥梁的最大承载量，不幸的是，他不知道如何找到最大运输重量。请你帮助Hugo，给你城市的规划图，描述了各交叉点之间的街道（具有最大承载量），交叉点的编号从1到n。你的任务是找到从1（Hugo的位置）到n号（客户的位置）交叉点可以运输的最大重量，你可以假设至少有一条路径。所有街道都是双向通行。输入格式：第一（城市图）。对于每个城市，第一行给出街道交叉点的数量n（1≤n≤1000）和街道的数量m，以下m行每行是一个整数三元组，指定街道开始和结束交叉点编号和允许的最大重量，它是正数且不大于1000000，每对交叉点之间最多只有一条街道。输出格式：每个场景的输出以"Scenro#："开头，其中是从开始的场景编号，然后输出一行，其中包含Hug个空行表示输出结束。答：prtvng*;prtvu*;csNde //优先队列（按d大根堆）中结点类型{ntv; //顶点编号ntd; //dv值pubcNdentvntd) //构造方法{hv=v;hd=d;}}csENde //边类{ntv; //邻接点nt; //边权值ntnex; //下一条边ENdentvnt) //构造方{h=;}}pubccsn{cnlntINF=x;//表示∞cnlnt=; //表示最多顶点个数cnlntE=*;//表示最多顶点个数cnt;cn]hed=newn;cENde]edge=newENdeE;cntn;cvdddEdgentuntvnt)//无向图添加<uv和<vu>{edge=newENdev;//添加边<uv>edgenex=hedu;hedu=++;edge=newENdeu;//添加边<vu>edgenex=hedv;hedv=++;}pubccntkrntv)//求从v到其他顶点的最短路径{Cprr<Nde>dCprr//定义dCprr=newCprr<Nde>){pubcntcpreNdeNde)//用于创建d大根堆{reurndd;}};rryQueue<Nde>pq=newrryQueue<Nde>dCprr;nd=newn;//建立d数组n]S=newn; //建立S数rryd; //初始化d]rryS;dv=INF; //源点到自己的最大承载量看成∞pqernewNdevdv;//将顶点v进队pqhepqEpy) //队不空循环{Ndep=pqp; //出队结点pntu=pv; //选取具有最大d的顶点ufSu==)cnnue;//跳过S中的顶点uSu=; //顶点u加入S中fu==n)brek; //找到顶点n，结束rnte=hedu;e=;e=edgeenex){ntv=edgeev; //找到边nt=edgee;fSv==) //修改不在S中的顶点v的dfdv]<hndu{dv=hndu;pqernewNdevdv;}}}reurndn;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntb;=nnexIn;rntk=;k<=;k++){rryhed;=;n=nnexIn;=nnexIn;rnt=;i<=;++) //输入条边的信息{=nnexIn;b=nnexIn;=nnexIn;ddEdgeb;}Syeuprn"Scenro#%d:\n"k;//输出结果Syeuprn"%d\n\n"kr;}}}.OJ—股票经纪人的小道消息问题时间限制：，空间限制：。问题描述：众所周知，股票经纪人对谣言会反应过度。你已经签约开发一种在股票经纪人中传播虚假信息的方法，以便为你的雇主提供股票市场的战术优势。为了达到最大效果，你必须以最快的方式传播谣言。不幸的是，股票经纪人只信任来自他们“可信来源”的信息，这意味着你必须在传播谣言时考虑他们的联系人的结构。特定的股票经纪人需要一定的时间才能将谣言传递给他的每个同事。你的任务是编写一个程序，告诉你选择哪个股票经纪人作为谣言的起点，以及谣言传播到股票经纪人社区所需的时间。该持续时间是指最后一个人接收信息所需的时间。输入格式：你的程序将为不同的股票经纪人输入数据。每组都以一条包含股票经纪人数量n的行开头，接下来每行一个股票经纪人，其中包含与之联系的人数，这些人是谁，以及他们将消息传递给每个人所花费的时间。每个股票经纪人行的格式如下：该行以联系人数量（m）开头，后跟n对整数，每个联系人一对。每一对首先列出一个指代联系人的号码（例如1表示该组中的第一个号码），然后是用于将消息传递给该人的时间（以分钟为单位）。没有特殊的标点符号或间距规则。每个人的编号为1到股票经纪人的数量。传递消息所需的时间将介于1到10分钟（包括1和10分钟）之间，联系人数量将介于0到股票经纪人的数量减1之间。股票经纪人的数量范围从1到100，输入由一组包含0个股票经纪人终止。输出格式：对于每组数据，你的程序必须输出一行，其中包含导致最快消息传输的人，以及在你将该消息传递给此人之后最后一个人收到任何给定消息的时间，以整数分钟为单位。你的程序可能会收到一个排除某些人的连接网络，即某些人可能无法访问。如果你的程序检测到这样一个破碎的网络，只需输出消息dn。注意，将消息从传递给所花费的时间不一定与将其从传递给所花费的时间相同。答：prtvng*;prtvu*;prtvuScnner;pubccsn{cnlnt=; //表示最多经纪人个cnlntINF=x; //表示∞cn]=newn;//数组，初始为邻接矩阵cntn; //经纪人个数pubccvdFyd //Fyd算法{rntk=;k<=n;k++) //求k]{rnt=;i<=n;++)rnt=;j<=n;++)f=j&>k+k)=k+k;}}pubccvddpn //求结果并且输出{ntx;ntntnv=;rnt=;i<=n;++) //以点作为各通路源点{x=;rnt=;j<=n;++)=j&x< //找到x=;n>x){n=x; //找最长路径中的最短路径长nv=; //该最短长度路径的源点}}n<NF) //源点nvSyeuprnnnv+""+n;ee //源点nvSyeuprnn"dn";}pubccvdnSrng]rg){Scnnern=newScnnerSyen;henhNex){n=nnexIn;fn==)brek;rnt=;i<=n;++) //rnt=;j<=n;++)f==)=;ee=INF;rnt=;i<=n;++) //输入邻接矩阵A{nt=nnexIn;rnt=;j<=;++){ntp=nnexIn;nt=nnexIn;p=;}}Fyd; //调用Fyd算法求Adpn; //求nv和n并且输}}}H—重新排列指令问题时间限制：，空间限制：。问题描述：阿里本学期开设了计算机组织与架构课程，他了解到指令之间可能存在依赖关系，如WAR（写入后读取），WAW，RAW。如果两个指令之间的距离小于安全距离（Sence），则会导致危险，这可能导致错误的结果，所以需要设计特殊的电路以消除危险。然而，解决此问题的最简单方法是添加气泡（无用操作），这意味着浪费时间以确保两条指令之间的距离不小于安全距离。两条指令之间距离的定义是它们的开始时间之间的差异。现在有很多指令，已知指令之间的依赖关系和安全距离。我们有一个非常强大的CPU，具有无限数量的内核，因此你可以根据需要同时运行多个指令，并且CPU速度非常快，只需花费1ns即可完成任何指令。你的工作是重新排列指令，以便CPU可以使用最短的时间完成所有指令。输入格式：输入包含几个测试用例。每个测试用例的第一行是两个整数n，（n≤，≤），表示有n个指令和m个依赖关系，以下m行，每行包含三个整数x，y，z，表示x和y之间的安全距离为z，y应在x之后运行。指令编号从0到n-1。输出格式：每个测试用例打印一个整数，即CPU运行所需的最短时间。答：prtvng*;prtvu*;prtvuScnner;csENde //边类型{ntv; //邻接点nt; //边权值ntnex; //下一条边ENdentvnt) //构造方{h=;}}pubccsn{cnlntINF=x; //表示∞cnlnt=; //表示最多顶点个数cnlntE=*;//表示最多顶点个数cnt;cn]hed=newn;cENde]edge=newENdeE;cnnd=newn; //记录每个顶点的入度cnc=newn; //记录到顶点cntn;cvdddEdgentuntvnt)//有向图添加边<uv>{edge=newENdev;edgenex=hedu;hedu=++;ndv++; //顶点v的入度增1}pubccvdpSr //拓扑排序{Sck<neger>=newSck<neger>;//定义一个栈rnt=;i<n;++) //所有入度为的顶点进栈fnd==){puh;c=; //路径经过顶点，长度计为1}heepy //栈不为空时循环{ntu=pp; //出栈一个顶点urnte=hedu;e=;e=edgeenex){ntnt=edgee;ndv;cv=hxcvcu+;fndv==) //入度为的顶点进栈st.push(v);}}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;henhNex){rryhed; //=;rrynd; //顶点入度初始化rryc; //顶点的最长路径长度初始n=nnexIn;=nnexIn;rnt=;i<=;++) //输入边的信息{ntu=nnexIn;ntv=nnexIn;nt=nnexIn;ddEdgeuv;}TopSort();ntrnt=;i<n;++) //cn=hxnc;Syeuprnnn;}}}OJ—城堡问题时间限制：，空间限制：。问题描述：如图所示的城堡中#表示墙，请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大？城堡被分割成n（≤，n≤）个方块，每个方块可以有~面墙。输入格式：程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字（0≤p≤50）描述，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块的数字是其周围墙的数字之和表示。城堡的内墙被计算两次，方块（1，1）的南墙同时也是方块（2，1）的北墙。输入的数据保证城堡至少有两个房间。输出格式：输出两个整数，前者表示城堡的房间数，后者表示城堡中最大房间包括的方块数。答：prtvng*;prtvu*;prtvuScnner;pubccsn{cnt=; //最大行列数cnp=newn;//存放方块cncr=newn;//方块是否染过色cntNu=xre=;//房间数和最大方块数cntre; //当前房间的方块数cvdFSntnt) //从查找包含它的房间{cr=) //已经染过色，返回return;re++; //颜色数增加1cr=Nu;p]&==) //没有西墙FS;p]&==) //没有北墙FS;p]&==) //没有东墙FS+;p]&==) //没有南墙FS+;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;=nnexIn;n=nnexIn;rnt=;i<=;++)rnt=;j<=n;++)p=nnexIn;rnt=;i<=;++)rnt=;j<=n;++)fcr==){Nu++;re=;//房间的方块数初始化为0FS;xre=hxxrere;}SyeuprnnNu;Syeuprnnxre;}}四、简答题.某城市道路中大部分是双向马路，有少部分是单向马路。现构建该城市道路交通网用于道路规划，包括道路查找等。问是设计成有向图还是无向图？是带权图还是不带权图？答：因为城市道路中有单向马路，只能用有向边来表示，双向马路可以转换成两条有向边。另外，在道路规划中涉及马路的长度，所以该城市道路交通网应设计成带权有向图。有一个无向连通图，对于给定的某种邻接表表示，能否通过修改深度优先遍历算法求出所有的深度优先遍历序列？ 答：不能。对于给定的无向连通图邻接表，其表示是不唯一的，不同的邻接表，通过修改深度优先遍历算法只能求出该邻接表下所有的深度优先遍历序列，除非构建所有可能的邻接表，才可能求出所有的深度优先遍历序列。图的遍历针对顶点，要求按一定顺序访问图中所有顶点，且每个顶点仅访问一次。可否针对边也使用遍历算法？ 答：可以。用二维辅助数组ved来记录一条边是否访问过，初始时所有元素为。可以从任一顶点出发，对于访问的一条边<>，置ved]=表示该边已访问过，下次再找相邻边<k>时只有在vedk为时才从顶点k出发进行递归调用。整个过程与顶点遍历的深度优先过程相同。图的遍历对无向图和有向图都适用吗？ 答：图的遍历对无向图和有向图都适用。但如果无向图不是连通的，或有向图不是强连通的，调用一次遍历算法只能访问一个连通分量或强连通分量中的顶点，这种情况下需要多次调用遍历算法。图的深度优先遍历类似于树的先根遍历，可归属哪一类算法？ 答：图的深度优先遍历类似于树的先根遍历，都属于回溯算法。由于图的深度优先遍历有可能在访问某个顶点后，沿着某条路径向前搜索又回到这个顶点，所以要设置一个访问标记数组ved记录已访问过的顶点，以避免重复访问，而树的先根遍历没有这种情形出现。对于一个具有n个顶点的连通无向图，如果它有且只有一个简单回路，那么该图有几条边？为什么？ 答：该图有n条边。因为具有n个顶点n-1条边的连通无向图是树图，它没有任何回路，但两个顶点i和j之间有路径，如果加上一条边(i,j)，则形成一个简单回路，如果再加上一条边，则会形成两个简单回路。所以这样的图恰好有n条边。7.有一个如图8.1（a）所示的有向图，回答以下问题：（1）给出该图的所有强连通分量。（2）给出从顶点0到顶点的所有简单路径。答：（）该有向图的强连通分量如图（b）所示，共有个强连通分量。（2）顶点0到顶点的所有简单路径如下：0→1→4→80→3→7→80→3→1→4→88.有一个如图8.2（a）所示的有向图，给出其所有的强连通分量。答：图中顶点0、1、2构成一个环，这个环一定是某个强连通分量的一部分，图中顶点3、4构成一个环，这个环也一定是某个强连通分量的一部分，这两个环合在一起后能不能构成一个强连通分量呢？通过判断它们能够构成一个强连通分量。另外，顶点5、6各自构成一个强连通分量。该有向图的强连通分量有个，如图（b）所示。9.一个图有7个顶点，编号为0～6，其邻接矩阵如下： 回答以下问题：（1）画出该有向图。（2）求顶点0的入度和出度。求顶点2的度。答：（）该有向图如图所示。顶点0的入度为0，出度为3。顶点2的度为5。图是一个非连通无向图，共有条边，则该图至少有多少个顶点？ 答：由于G是一个非连通无向图，在边数固定时，顶点数最少的情况是该图由两个连通子图构成，且其中之一只含一个顶点，另一个为完全图。其中只含一个顶点的子图没有边，另一个完全图的边数为nn/，即：nn/=，得：n=。所以，该图至少有+=个顶点。使用普里姆算法构造出如图所示的图的一棵最小生成树。答：11.已知带权连通图=（E）的邻接表如图所示，请画出该图的逻辑结构，并分别以深度优先和广度优先遍历该图，写出遍历中顶点的序列，并画出该图的一棵最小生成树，其中表结点的个域各为：答：该图的逻辑结构如图所示。从顶点1出发的深度优先遍历序列为：0、1、2、3、4。从顶点1出发的广度优先遍历序列为：0、1、2、3、4。采用普里姆算法（从顶点出发）或克鲁斯卡尔算法求得的最小生成树如图所示。给出如图所示的图中从顶点开始的深度优先生成树，并求出最小生成树。答：从顶点0开始的深度优先遍历序列很多，每一序列都生成一棵DFS树，除去重复的，其深度优先生成树及权值之和如下：，，，，，权值和为++++=1，，，，，权值和为++++=2，，，，，权值和为++++=3，，，，，权值和为++++=4，，，，，权值和为++++=5，，，，，权值和为++++=1，，，，，权值和为++++=2，，，，，权值和为++++=5，，，，，权值和为++++=1，，，，，权值和为++++=8，，，，，权值和为++++=4其最小生成树为，，，，。13.对于如图所示的带权无向图，给出利用普里姆算法（从顶点开始构造）和克鲁斯卡尔算法构造出的最小生成树的结果。答：利用普里姆算法从顶点出发构造的最小生成树为：。利用克鲁斯卡尔算法构造出的最小生成树为：。

14.对于如下图所示的带权有向图，采用Dijkstra算法求出从顶点0到其他各顶点的最短路径及其长度。答：采用Dijkstra算法求从顶点0到其他各顶点的最短路径及其长度如下：从0到1的最短路径长度为1，最短路径为0->1。从0到2的最短路径长度为4，最短路径为0->1->2。从0到3的最短路径长度为2，最短路径为0->3。从0到4的最短路径长度为8，最短路径为0->1->4。从0到5的最短路径长度为10，最短路径为0->3->5。15.对于如下图所示的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪个村庄能使各村庄总体的交通代价最小？答：采用Floyd算法求出两顶点之间的最短路径长度，其邻接矩阵如下：A=最后求得：

A从A4中求得每对村庄之间的最少交通代价。假设医院建在村庄i，其他各村庄往返总的交通代价如下表所示。显然把医院建在村庄3总的交通代价最少。医院建在的村庄各村庄往返总的交通代价012+16+4+7+13+16+4+18=90113+29+17+20+12+11+8+5=115216+11+12+6+16+29+12+34=13634+8+12+3+4+17+12+22=82418+5+34+22+7+20+6+3+0=11516.已知世界大城市为：北京（）、纽约（N）、巴黎（）、伦敦（）、东京（）、墨西哥城（）。试在由表给出的交通网中确定最小生成树，并说明所使用的方法及其时间复杂度。表1世界大城市交通里程网络表单位:k)答：构成的无向图如图所示。产生的最小生成树如图所示。使用普里姆算法的时间复杂度为On，其中n为图中顶点个数。使用克鲁斯卡尔算法的时间复杂度为Oege，其中e为图的边数。17.给出如下图所示有向图的所有拓扑序列。答：拓扑序列有aebcd、abced、abecd。18.如下图所示的AOE网，求：（1）每项活动ai的最早开始时间e（ai）和最迟开始时间l（ai）。（2）完成此工程最少需要多少天（设边上的权值为天数）。（3）哪些是关键活动。（4）是否存在某项活动，当其提高速度后能使整个工程缩短工期。答：（1）该图的一个拓扑序列为1，2，3，4，5，6，7，8，9，10。按此次序求所有事件的最早发生时间如下： ve(1)=0 ve(2)=5 ve(3)=6 ve(4)=MAX{ve(2)+3,ve(3)+6}=12 ve(5)=MAX{ve(3)+3,ve(4)+6}=15 ve(6)=ve(4)+4=16 ve(7)=ve(5)+1=16 ve(8)=ve(5)+4=19 ve(9)=MAX{ve(7)+5,ve(8)+2}=21 ve(10)=MAX{ve(6)+4,ve(9)+2}=23按拓扑排序的逆序求所有时间的最迟发生时间如下：vl(10)=23 vl(9)=vl(10)-2=21 vl(8)=vl(9)-2=19vl(7)=vl(9)-5=16 vl(6)=vl(10)-4=19 vl(5)=MIN{vl(7)-1,vl(8)-4}=15 vl(4)=MIN{vl(6)-4,vl(5)-3}=12vl(3)=MIN{vl(4)-6,vl(5)-3}=6 vl(2)=vl(4)-3=9 vl(1)=MIN{vl(2)-5,vl(3)-6}=0求所有活动的e()、l()和d()如下：活动a1：e(a1)=ve(1)=0 l(a1)=vl(2)-5=4 d(a1)=4活动a2：e(a2)=ve(1)=0 l(a2)=vl(3)-6=0 d(a2)=0活动a3：e(a3)=ve(2)=5 l(a3)=vl(4)-3=8 d(a3)=3活动a4：e(a4)=ve(3)=6 l(a4)=vl(4)-6=6 d(a4)=0活动a5：e(a5)=ve(3)=6 l(a5)=vl(5)-3=12 d(a5)=6活动a6：e(a6)=ve(4)=12 l(a6)=vl(5)-3=12 d(a6)=0活动a7：e(a7)=ve(4)=12 l(a7)=vl(6)-4=15 d(a7)=3活动a8：e(a8)=ve(5