首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法求图的中心点。设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
2012-06-21
399
问题
设计一个算法求图的中心点。设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++)//实现()功能 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++)//实现()功能,结果放在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];//实现()功能,结果放在k中 for(i=1;i<G.n;i++) { if(B[i]<m) { m=B[i]; k=i; } return k;//返回k值 }
解析
转载请注明原文地址:https://kaotiyun.com/show/PNxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:()选拓龟板,印成(),这成为甲骨文的第一部著录之作,此后,甲骨
建设有中国特色的社会主义理论主要包括哪些内容?
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
下列不是美国独立战争与美国内战的相同点的是()。
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
在独立编址方式下,存储设备和I/O设备是()来区分的。
随机试题
为了解决CPU与外部设备的速度匹配问题,可采用_______。
在数据库系统中,原子数据是指不可再分的数据。()
主韧带为固定宫颈位置保持子宫不致下垂的主要结构。()
A.肺间质病变B.右下肺动脉干≥15mmC.尖端指向肺门的楔形阴影D.升主动脉扩张、膨隆E.多发性中下肺野结节及浸润
颈肌收缩时下降舌骨,并使喉上、下活动的肌群是
填写票据出票日期时,“2月12日”应填写成()。
组织劳动力的多样性是指()。
产生酸雨的主要原因是()。
Thediagrambelowshowshowgeothermalenergyisusedproduceelectricity.Summarisetheinformationbyselectingandreporting
Makingchoicesishard.ThatwouldbewhyresearcherMoranCerfhaseliminateditfromhislife.Asarule,healwayschoosesth
最新回复
(
0
)