首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为: MAx{从ω到v的最短距离|ω属于V(G)} 如果v是有向图G中具有最小偏心度的顶点,则称顶点v是G的中心点。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为: MAx{从ω到v的最短距离|ω属于V(G)} 如果v是有向图G中具有最小偏心度的顶点,则称顶点v是G的中心点。
admin
2017-01-04
25
问题
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:
MAx{从ω到v的最短距离|ω属于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[btAXV]; 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=1;i<G.n;i++) { if(B[i]<m) { m=B[i]; k=i; } } retum k: //返回k值 }
解析
转载请注明原文地址:https://jikaoti.com/ti/S6fjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述美苏争霸的三个阶段,并分析其影响与教训。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
在下列哪个条约中,最先出现了片面最惠国待遇()。
在周初分封中,分封同姓诸侯国、异姓诸侯国,也分封圣王之后,下面属于圣王之后的封国为()。
下面哪部经典是我国最早的官方史书?()
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
在下面的应用中,通常使用栈的是()。 Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值
随机试题
毛果芸香碱对眼的作用是:
小肠吸收的有利条件是
下列哪项体征不是Homer征
女性,32岁。胸闷、气短10天,伴腹部不适,发热37.5℃,食欲下降,体重下降,无腹泻、恶心及呕吐。B超显示胸、腹腔积液。PPD皮试强阳性。首先应考虑的疾病
在房地产产权档案的整理和管理中,常用的档案号不包括()。
某土石坝开挖工程量为10万m3,经现场测量土石方体积比约为3:7;已知发包人并未要求对土石坝的表土和岩石分开开挖,且合同中该部位土方、石方开挖单价分别为10元/m3、20元/m3,则该部分土石坝开挖的结算价款应为()万元。
关于信贷资金运动的特征,下列说法错误的是()
海南居民语言种类多,主要使用的方言有海南话、黎话、临高话、儋州话、军话等10多种。()
西汉修“五尺道”,在云南派官置吏,标志着中央王朝对云南正式统治的开始。()
对于循环队列,下列叙述中正确的是()。
最新回复
(
0
)