首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法求图的中心点。设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
401
问题
设计一个算法求图的中心点。设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
学硕统考专业
相关试题推荐
简要概括基督教的演变。
对巴黎公社的评述,正确的有()。①是无产阶级建立政权的第一次伟大尝试②主要的经验是废除旧的国家机器,建立新的国家机器③其实践和经验,丰富了马克思主义理论④由于无产阶级的不成熟,其失败是不可避免的
法西斯势力上台后,英国面对挑战一心推行绥靖政策。其主要目的是()。
西汉时期最后写定的()一书,包括《素问》与《灵枢》(或称《针经》)两部分,是中国最早的一部医书。
德国法西斯能够通过合法方式夺取政权,主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党
毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
请根据下面材料,结合相关知识,分析其内容及意义。他命令所有罗马人都进行登记并用银对自己的财产估价,按照习惯宣誓保证所报各项均属真实,全部财产均已按最高价格估价,并陈报父亲系何人,自己的年龄,自己的妻子和子女的名字,每人的籍贯隶属市中哪个部落或乡间
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
某汽车轮渡口,过江渡船每次能载10辆车过江。过江车辆分为客车类和汽车类,上渡船有如下规定:同类车先到先上船,客车先于货车上船,且每上4辆客车,才允许上一辆货车,若等待客不足4辆,则以货车代替,若无货车等待允许客车都上船。写一算法模拟渡口管理。
随机试题
驾驶机动车在雨天临时停车注意什么?
下列作品不属于余秋雨的是()
A.细动脉玻璃样变B.细动脉纤维化C.细动脉淀粉样变性D.细小动脉纤维素样坏死良性高血压的基本病变是
有关硝普钠的叙述,错误的是
隔墙的隔声性能,与墙体材料的密实性、构造连接的严密性及墙体的吸声性能有关,将下列墙体的隔声性能优劣按其计权隔声量排序,试问哪组是错误的?[2003年第087题]Ⅰ.125mm加气混凝土砌块墙,双面抹灰各20mm厚Ⅱ.120mm承重实心黏
2017年4月,申请执行人B公司请求甲地级市乙县人民法院执行人A公司(住所地为丙地级市丁县)位于乙县的X房产。乙县人民法院在执行中发现,A公司不能清偿到期债务且资产不足以清偿全部债务。后经A公司书面同意,该执行案件移送破产审查。同年5月,受移送人民法院确定
设计评审是一种()的正规审查程序。
若行列式=().
英国产业革命首先是从纺织工业部门开始的。()
根据下面文字资料,回答第121~130题。仔细阅读下面资料,回答以下问题:恩格尔系数,即食品消费支出在总消费支出中所占的比重。联合国粮农组织依据恩格尔系数,将生活水平划分为如下标准:恩格尔系数在59%以上者为绝对贫困状态的消费;50%~59%为
最新回复
(
0
)