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

admin2018-08-12  34

问题 设计一个算法求图的中心点。设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/6MRi777K
0

最新回复(0)