首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为: MAX{从w到v的最短距离∣w属于V(G)} 如果v是有向图G中具有最小偏心度的顶点,则称顶点v是G的中心点。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为: MAX{从w到v的最短距离∣w属于V(G)} 如果v是有向图G中具有最小偏心度的顶点,则称顶点v是G的中心点。
admin
2019-08-15
66
问题
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:
MAX{从w到v的最短距离∣w属于V(G)}
如果v是有向图G中具有最小偏心度的顶点,则称顶点v是G的中心点。
选项
答案
设C是有向图G的邻接矩阵,求最小偏心度的顶点的步骤如下: (1)利用Floyd算法求出每对顶点之间的最短路径矩阵A; (2)对矩阵A求出每列i的最大值,得到顶点i的偏心度; (3)在这n个顶点的偏心度中,求出最小偏心度的顶点k,即为图G的中心点。 对应的算法如下: int Center(MGraph&G) { int A[MAXV][MAXV],B[MAXV]; int i,j,k,m; for(i=0;i<G.n;i++) //将邻接矩阵赋给A for(j=0;j<G.n;j++) A[i][j]=G.edges[i][j]; for(k=0;k<G.n;k++) //实现(1)功能,求出每对顶点之间的最短路径 for(i=0;i<G.n;i++) for(j=0;j<G.n;j++) if(A[i][k]+A[k][j]<A[i][j]) A[i][j]:A[i][k]+A[k][j]; for(j=0;j<G.n;j++) //实现(2)功能,得出矩阵A每列最大值,即顶点i的偏心度,结果放在B数组中 { B[j]=A[0][j]; for(i=1;i<G.n;i++) if(B[j]<A[i][j]) B[j]:A[i][j]; } k=0: m=B[j]; //实现(3)功能,找出n个顶点中偏心度最小的顶点,结果放在k中, //即为图G的中心点 for(i=l;i<G.n;i++) { if(B[i]<m) { m:B[i]; k=i; } } return k; //返回k值 }
解析
转载请注明原文地址:https://kaotiyun.com/show/MdCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赵匡胤了解高级将领发动兵变夺取政权的危险,他注意分散军权。回答问题:建隆二年,赵匡胤采取了()的措施,收夺武将的兵权
关于塞尔维乌斯改革的叙述中,不正确的是()。
1956年召开的中共八大指出,我国国内主要矛盾的实质是()。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
快速排序最易发挥其长处的情况是()。
某模型机的通路结构如下图所示,用寄存器传送语句(如PC→MAR),拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0),Y(R1),源和目的操作数地址均采用变址寻址,第1个参数X为源操作数的形式地址,第2个参数为目的操作数的形
设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数是()。
已知无向网G的邻接矩阵如下图所示,要求:(1)请画出该网;(2)画出基于该邻接矩阵的网G的宽度优先搜索生成树;(3)按克鲁斯卡尔算法给出G的一棵最小生成树的生成过程(要求给出步骤)。
随机试题
IngmaBergman’slatestworkasascreenwriteris"Sunday’sChildren".SetinruralSwedenduringthelate1920s,thestorycent
材料切削加工性是通过采用材料的硬度、抗拉强度、伸长率、冲击值、热导率等进行综合评定的。()
患者,男性,32岁,MRI检查发现左上颌窦腔内异常信号灶。图像如下,最可能的诊断为
石菖蒲的药用部位为( )。
一个有10个数据的样本,它们中的每一个分别与20相减后所得的差相加是100,那么这组数据的均值是()。
附带民事诉讼应当同刑事案件一并审判。()
我国实施国家信息化的总体思路之一是:全面推动领域信息化和()进程。
根据下面材料回答下列题:2007年劳动力需求最少的五个行业的劳动力总需求占我国劳动力总需求的比重是()。
男性,68岁。不慎跌倒,感左髋部疼痛。体检:左下肢短缩2cm、极度外旋畸形。常常提示
规模经济与规模不经济的原因。
最新回复
(
0
)