首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法求图的中心点。设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
68
问题
设计一个算法求图的中心点。设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
学硕统考专业
相关试题推荐
在国民政府统治下的中国民族经济发展缓慢的原因不包括()。
鸦片战争失败后,西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点,对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:第二次鸦片战争结束后,外国军舰和商船沿长江最远可到达()
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
某会议有n个参与者,等大家到齐后会议才能开始,利用P、V原语操作实现会议参与者进程。
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
已知小写英文字母“a”的ASCⅡ码值为61H,现字母“g”被存放在某个存储单元中,若采用偶校验(假设最高位作为校验位),则该存储单元中存放的十六进制数是()。
假定不采用Cache和指令预取技术,且机器处于“开中断”状态,则在下列有关指令执行的叙述中,错误的是____。
下列叙述中,不符合m阶B树定义要求的是____。
若对n阶对称矩阵A[1..n,1..n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1..n(n+1)/2]中,则在B中确定aij(i
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
2015年,某市非公有制经济实现增加值348.12亿元,比上年净增加23.69亿元,非公有制经济增加值占该市GDP的比重为57.5%。其中,民营经济增加值335.24亿元,外商经济增加值11.84亿元,港澳台经济增加值1.04亿元,分别比“十一五”(201
ThePrimeMinisterMargaretThatcherbelievedinthefollowingexcept______.()
财务比率主要分为哪几类()。
如某投资组合由收益呈完全负相关的等量两只股票构成,则()。
A、 B、 C、 D、 C题干图形基本相似,初步判断是图形的细节变换。但从行间和列间均无法找到合适的叠加规律。注意到题干所求图形位于中间位置,从九宫格整体来看,四条对称轴上位置对称的两个方框中的图形叠加,阴影
简述遗嘱的有效条件。
2018年宪法修正案中,取消了下列哪项的任期限制()
洛杉矶市市长任命了一名黄种人当教育厅厅长,许多白种人和黑种人指责这一任命是为了显示种族平等的政治姿态。后来市长又任命了一名黑人商人担任市财政总监,许多白种人和黄种人又做出了同样的指责。的确,在很大程度上,市长作上述任命时是处于政治考虑,但这又有什么错呢?做
材料1现在摆在中国人民、各民主党派、各人民团体面前的问题,是将革命进行到底呢,还是使革命半途而废呢?如果要使革命进行到底,那就是用革命的方法,坚决彻底干净全部地消灭一切反动势力,不动摇地坚持打倒帝国主义,打倒封建主义,打倒官僚资本主义,在全国范围
设f(2x+1)=xex,则=_______.
最新回复
(
0
)