问题
问答题
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为： MAX{从w到v的最短距离|w属于V(G)} 如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是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值
}