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

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

admin2017-01-04  42
问题 设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：
    MAx{从ω到v的最短距离|ω属于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[btAXV]； 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=1；i＜G．n；i++) { if(B[i]＜m) { m=B[i]； k=i； } } retum k： ／／返回k值 }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/HQRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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