首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法求图的中心点。设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
88
问题
设计一个算法求图的中心点。设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://www.kaotiyun.com/show/MdCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
庆历新政是统治集团内部为了改革弊病而进行的一次努力。回答问题:庆历新政的中心内容是()
赫鲁晓夫执政时期,为了解决粮食问题,除了开展垦荒运动以外,在农村还开展了()。
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
下面关于进程的叙述中,正确的是()。
在TELNET协议中,用户发送的命令采用TCP传输到服务器,在TCP的数据包中,需要把()符号位置移位,从而使服务器尽快响应命令。
设结点x和y是二叉树中任意的两个结点,在该二叉树的先序遍历序列中x在y之前,而在其后序遍历序列中x在y之后,则x和y的关系是()。
假定变量i、f和d的数据类型分别为int、float和double(int用补码表示,float和double分别用IEEE754单精度和双精度浮点数格式表示),已知i=785,f=1.5678e3,d=1.5e100。若在32位机器中执行下列关系表达式,
随机试题
切换
女性,50岁,患耐青霉素G的金葡菌性心内膜炎,青霉素试敏阴性,既往有慢性肾盂肾炎,治疗该患者应选用
社会正义
题26~30:某地上16层商住楼,地下2层(未示出),系底层大空间剪力墙结构,如图5-28所示(仅表示1/2,另一半对称),2~16层均布置有剪力墙,其中第①、④、⑦轴线剪力墙落地,第②、③、⑤、⑥轴线为框支剪力墙。该建筑位于7度地震区,抗震设防类别丙
根据仲裁法律制度的规定,当事人提出证据证明裁决有依法应撤销情形的,可以在收到裁决书之日起一定期间内,向仲裁委员会所在地的中级人民法院申请撤销裁决,该期间为()。
青海是()的发源地,故被称为“江河源头”,又称“三江源”。
关于康复权的总体方针,下列说法错误的是()。
城市的个性一旦形成便很难改变,它是一种历史的产物和文化的__________。人们常常通过一条小小街道和别致的建筑物就能__________一座城市的性格特征,但只有当人与城市处于一种__________的状态的时候,城市的个性魅力才会真正放射光彩。填入划
[*]
Theguyinthenextcubicleisyammeringawayonthephone.Acrosstheroom,someonebeginscursingloudlyatajammedcopymach
最新回复
(
0
)