2. 考研
  3. 设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

admin2013-09-16  80
问题 设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。
选项
答案设C是有向图G的邻接矩阵，求最小偏心度的顶点的步骤如下：(1)利用Floyd算法求出每对顶点之间的最短路径矩阵A；(2)对矩阵A求出每列i的最大值，得到顶点i的偏心度；(3)在这n个顶点的偏心度中，求出最小偏心度的顶点k，即为图G的中心点对应的算法如下： int Center(MGraph&G) { int AEMAXV]EMAXV]，B[MAXV]； int i，j，k，m； for(i=0；i
解析
转载请注明原文地址:https://kaotiyun.com/show/vcxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)