用C语言求图的中心顶点问题

下面是用 C 语言实现 Floyd 算法求解无向图中心顶点的代码示例：

#include <stdio.h>
#define INF 1000000 // 定义一个足够大的数作为无穷大

int G[1010][1010]; // 图的邻接矩阵
int dis[1010]; // 存储每个顶点到其他顶点的最短路径长度之和

int main()
{
    int n, m; // n 为顶点数，m 为边数
    scanf("%d%d", &n, &m);

    // 初始化邻接矩阵
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j) G[i][j] = 0;
            else G[i][j] = INF;
        }
    }

    // 读入边的信息，更新邻接矩阵
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u][v] = G[v][u] = w;
    }

    // Floyd 算法求解每个顶点到其他顶点的最短路径长度之和
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(G[i][k] + G[k][j] < G[i][j])
                {
                    G[i][j] = G[i][k] + G[k][j];
                }
            }
        }
    }

    // 找到最小的最短路径长度之和
    int minDis = INF;
    for(int i = 1; i <= n; i++)
    {
        dis[i] = 0;
        for(int j = 1; j <= n; j++)
        {
            if(G[i][j] != INF)
            {
                dis[i] += G[i][j];
            }
        }
        if(dis[i] < minDis)
        {
            minDis = dis[i];
        }
    }

    // 输出中心顶点
    int center = 0;
    for(int i = 1; i <= n; i++)
    {
        if(dis[i] == minDis)
        {
            if(center == 0 || dis[i] < dis[center])
            {
                center = i;
            }
        }
    }
    printf("图的中心顶点为：%d\n", center);

    return 0;
}

在这个示例代码中，我们首先读入图的顶点数和边数，然后根据边的信息更新邻接矩阵。接着，我们使用 Floyd 算法求解每个顶点到其他顶点的最短路径长度之和，并记录下最小值。最后，我们遍历每个顶点的最短路径长度之和，找到其中等于最小值的顶点中编号最小的一个，即为图的中心顶点。