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的中心点。

admin2012-06-21  425
问题 设计一个算法求图的中心点。设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++)／／实现()功能 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++)／／实现()功能，结果放在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]；／／实现()功能，结果放在k中 for(i=1；i＜G．n；i++) { if(B[i]＜m) { m=B[i]； k=i； } return k；／／返回k值 }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/PNxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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