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

admin2013-09-16  37

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

选项

答案设C是有向图G的邻接矩阵,求最小偏心度的顶点的步骤如下:(1)利用Floyd算法求出每对顶点之间的最短路径矩阵A;(2)对矩阵A求出每列i的最大值,得到顶点i的偏心度;(3)在这n个顶点的偏心度中,求出最小偏心度的顶点k,即为图G的中心点对应的算法如下: int Center(MGraph&G) { int AEMAXV]EMAXV],B[MAXV]; int i,j,k,m; for(i=0;i
解析
转载请注明原文地址:https://kaotiyun.com/show/vcxi777K
0

最新回复(0)