Prim算法

最小生成树问题一定是针对无向图，Prim算法适用于稠密图

存储结构采用邻接矩阵，n为顶点数，m为边数

int graph[n][n];

memset(graph, 0x3f, sizeof(graph));
for (int i = 0; i < n; i++) graph[i][i] = 0;

dis[i]标示顶点i到生成树的最短距离，以顶点0为开始构造生成树（初始化dis[0]为0，其他为0x3f3f3f3f），vis[i]标示顶点i是否已在生成树中（0是未访问，1是已访问，初始化为全0）

int dis[n], vis[n];

Prim算法流程如下：

(1)遍历所有未被访问的顶点j（vis[j]为0），找到其中距离生成树最近的顶点t（dis[t]为最短）

(2)标记t为已访问（vis[t]标记为1），用顶点t更新所有未访问顶点j的dis[j]（如果graph[t][j] < dis[j]，则用graph[t][j]更新dis[j]）

(3)循环1、2步n-1次（每次标记一个顶点已访问，除开始选取的顶点0一共n-1个顶点需要标记，所以循环n-1次）

for (int i = 1; i < n; i++) {
    int t = -1;
    for (int j = 0; j < n; j++)
        if (!vis[j] && (t == -1 || dis[j] < dis[t])) t = j;

    vis[t] = 1;
    for (int j = 0; j < n; j++)
        if (!vis[j]) dis[j] = min(dis[j], graph[t][j]);
}

算法结束时，dis[i]存储顶点i被加入生成树选出的最小边的权值，将所有顶点i的dis[i]相加得到最小生成树的边权和，若dis[i]有0x3f3f3f3f则没有最小生成树

---