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

admin2019-08-15  45

问题 设计一个算法求图的中心点。设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://kaotiyun.com/show/MdCi777K
0

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