2. 考研
  3. 设计一个算法求图的中心点。设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的中心点。

admin2016-03-29  82
问题 设计一个算法求图的中心点。设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
解析
转载请注明原文地址:https://kaotiyun.com/show/XmRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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