首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法求图的中心点。设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
47
问题
设计一个算法求图的中心点。设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
学硕统考专业
相关试题推荐
赵匡胤了解高级将领发动兵变夺取政权的危险,他注意分散军权。回答问题:建隆二年,赵匡胤采取了()的措施,收夺武将的兵权
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
某阅览室晚间开放,第一个进入的读者开灯,最后一个离开的读者关灯。利用P、V原语操作实现读者进程。
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
若对n阶对称矩阵A[1..n,1..n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1..n(n+1)/2]中,则在B中确定aij(i
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
假定一组元素序列为{38,42,55,15,23,44,34,74,45,26},按次序插入每个元素生成一棵平衡二叉树,那么最后得到的平衡二叉树中度为2的结点个数为()。
偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中,不属于偏移寻址方式的是_______。
随机试题
小芹是初中二年级的女生,智力正常,人际关系良好,上课和平时作业都比较认真,学习总体成绩在班级处于中等水平,但是自信心有些不足。这次期中考试,她的其他课程考试发挥正常,只有数学没有考及格。她认为数学没有考好是因为她比别人笨,即使她再努力,数学也是学不好。
男孩,3岁,自幼人工喂养,食欲极差,有时腹泻,身高85cm,体重7500g,皮肤干燥、苍白,腹部皮下脂肪厚度约0.3cm,脉搏缓慢,心音较低钝。其主要诊断应是
分子中含苯并咪唑结构,通过拮抗外周多巴胺D2受体而发挥止吐作用的药物是()。
企业在安全生产中,各管理机构之间、各种管理制度和方法之间,必须具有紧密的联系,形成相互制约的回路,才能有效。这体现了()原则的应用。
板厚度一般为板跨度的(),且不小于()mm。
多元化投资组合的作用有()。Ⅰ.借助于资金庞大的优势使每个投资者面临的投资风险变小Ⅱ.借助于投资者众多的优势使每个投资者面临的投资风险变小Ⅲ.利用不同投资对象之间收益率变化的相关性,达到分散投资风险的目的Ⅳ.
下列各项股利政策中,股利水平与当期盈利直接关联的有()。
U会计师事务所在执业过程中,需要根据中国注册会计师职业道德概念框架处理与职业道德相关的事项,规范本所的执业行为。以下是U会计师事务所正在考虑的相关问题,请代为做出正确的专业判断。按职业道德基本原则的规定,会计师事务所的某些行为必须得到法律法规的许可,除
马克思把商品转换成货币称为“商品的惊险的跳跃”,“这个跳跃如果不成功,摔坏的不是商品,但一定是商品占有者”。这是因为只有商品变为货币()。
汇率变动对经济增长方式的棘轮效应
最新回复
(
0
)