* 假设T1集合是已加入最小生成树中的点，T2集合是剩下的待加入T2的点
* 我们要做的是把T2集合中离T1最近的那个点，加入T1
* 所以我们需要知道：
* 集合T2内各顶点到集合T1的距离
*
* 为此，我们用两个数组：
* cost[i]:用来表示T2中点i到T1的距离；
* pre[i]:用来表示T2中点i和T1中哪个点最近（为了输出加入时的路径，不输出路径则不需要此数组）
* visited[i]，代表i加入了T1集合
*
* NO.1
* 选取起始点v，将v加入T1,并对剩余各点进行距离初始化： initCost()
* NO.2
* 选择一个在T2集合中，距离T1集合最近的点k： findNext()
* NO.3
* 将k加入到集合T1中：visited[k] = 1
* NO.4
* 更新剩余T2中的各点到T1集合的距离
* （如果因为新加入的点k而使得T2中的点到T1的距离缩小，将此点的前导点改为k）
*if edge[k][i]<cost[i]
*then cost[i]=edge[k][i]; pre[i]=k;
*
* 这就完成了一次操作，加入一条边。
* 由于MST一定是n-1条边，进行n-1次后就完成了MST。
#include<stdio.h>
#include<string.h>
#define INF 0xfffffff// infinity
#define MAXSIZE 20
int num, n; // num: line; n: vertex
int edge[MAXSIZE][MAXSIZE]; // 邻接矩阵
int cost[MAXSIZE], pre[MAXSIZE], visited[MAXSIZE]; // 距离标记；前导点标记
// 所有数组从1开始
void Prim(int u);
int main()
{
int i, j;
int row, col, value;
memset(edge, 0, sizeof(edge));//void * memset (void * p,int c,size_t n);
scanf("%d%d", &n, &num);
for(i = 0; i < num; i++)// 构造邻接矩阵
{
scanf("%d%d%d", &row, &col, &value);
edge[row][col] = edge[col][row] = value;
}
for(i = 1; i <= n; i++) //将邻接矩阵对角线赋为0
for(j = 1; j <= n; j++)//原来就为0的赋为INF
if(i == j)
edge[i][j] = 0;
else if( edge[i][j] == 0 )
edge[i][j] = INF;
Prim(1); //Prim算法，不妨从顶点1开始
return 0;
}
//NO.1 对距离进行初始化
void initCost(int u)
{
int i;
for(i = 1; i <= n; i++)
{
cost[i] = edge[u][i];
pre[i] = u;
}
cost[u] = 0;
visited[u] = 1;
}
//NO.2 找到不在T1中，边的权值最小的那个点
int findNext()
{
int i;
int mincost = INF, v = -1;
for(i = 1; i <= n; i++)
{
if(visited[i] != 1 && cost[i] < mincost)
{
mincost = cost[i];
v = i;
}
}
return v;
}
//NO.4 加入后，对距离进行更新
void updateCost(int v)
{
int i;
for(i = 1; i <= n; i++)
{
if(visited[i] != 1 && edge[v][i] < cost[i])
{
cost[i] = edge[v][i];
pre[i] = v;
}
}
}
//在dijkstra算法中逆向打印点v到源点的路径
//在prim算法中不需要
void print_path(int v) //打印最短路的路径（反向）
{
while(v != pre[v]) //前驱
{
printf("%d<--", v);
v = pre[v];
}
printf("%d\n", v);
}
void Prim(int u)
{
int i, j;
int v = -1;
int weight = 0;
initCost(u); //NO.1 对距离进行初始化
for(i = 1; i < n; i++)//循环n-1次，加入n-1个顶点
{
v = findNext(); //NO.2 找到不在T1中，边的权值最小的那个点
if(v != -1) //如果找到那个点v
{
printf("%d--(%d)-->%d\n",
pre[v], cost[v], v); //打印加入的流程
visited[v] = 1; //NO.3 将v点加入T1
weight += cost[v];
updateCost(v);//NO.4 对距离进行更新
}
}
printf("The sum-weight of the MST is %d\n", weight);
//just for fun
print_path(7); //比如打印点7到源点的逆向路径玩玩儿=.=
}
相对于dijkstra而言，Prim最小生成树和Dijkstra最短路径的微小的差别为：“权值最低”的定义不同！
Prim的“权值最低”是相对于U中的任意一点而言的，也就是把U中的点看成一个整体，每次寻找V - U中跟U的距离最小（也就是跟U中任意一点的距离最小）的一点加入U；而Dijkstra的“权值最低”是相对于v0而言的，也就是每次寻找V-U中跟v0的距离最小的一点加入U。
因此对于最短路径，只要将上面MST的路径距离更新的代码改成以下部分（多加了lowcost[v]）：
if(visited[i] != -1 && edge[v][i] + cost[v] < cost[i])
{
cost[i] = edge[v][i] + cost[v];
pre[i] = v;
}
就OK了！
相对于Prim的复杂度O(n*n)，用Kruskal是个更简单也更好的选择，它的复杂度完全由排序决定。如果是用快排，则Kruskal的复杂度可以简化为O(n*logn)。
//Kruskal
#include<stdio.h>
#include<stdlib.h>
#define N 1010
typedef struct node
{
int begin, end; //这里的begin和end其实并没有“有向图”的概念，还是代表无向图
int value;
}Node;
Node edge[N]; //存储边的信息
int root[N]; //存储每个点所在的集合的根
int rising(const void *a, const void *b)
{
return ((Node *)a)->value - ((Node *)b)->value; //注意强制转型的优先级没有->高
}
int find(int point) //并查集的“查”
{
if(root[point] == -1) //如果根结点信息为-1，则自己就是自己所在集合的根
return point; //所以返回自己
return root[point] = find(root[point]); //否则压缩路径，并返回point所在集合的根=.=话说这一句信息量好大
}
//话说刚刚的return一次性将压缩路径和返回集合所在的根都解决了，相当于下面这个函数
/*
int pre[1000 ];
int find(int x) //查找根节点
{
int r=x;
while ( pre[r ] != r ) //找到根节点 r
r=pre[r ];
int i=x , j ;
while( i != r ) //路径压缩
{
j = pre[ i ]; // 在改变上级之前用临时变量 j 记录下他的值
pre[ i ]= r ; //把上级改为根节点
i=j;
}
return r ;
}
*/
void join(int x, int y) //并查集的“并”
{
if( find(x) != find(y) ) //如果两个点xy所在集合的根不一样，
root[ find(x) ] = find(y); //则将一个点合并到另一个集合（实际操作是置两个点的根为同一个根）
}
int main()
{
int n, m, i, sum = 0;
for(i=0; i<N; i++) //刚开始将所有的点的根初始化为-1
root[i] = -1;
scanf("%d%d", &n, &m);
for(i=0; i<m; i++)
scanf("%d%d%d", &edge[i].begin, &edge[i].end, &edge[i].value);
qsort(edge, m, sizeof(Node), rising); //按照边的权值快排nlogn
for(i=0; i<m; i++)
{
if( find(edge[i].begin) != find(edge[i].end) )//如果两个点不在一个集合，意味着连接两点不会成环
{
join(edge[i].begin, edge[i].end); //将一个点并到另一个点所在的集合
sum += edge[i].value;
}
}
printf("%d", sum);
return 0;
}