最小生成树（MST）

已知 n 个城市，并且已知它们之间的距离。问怎样修路才能保证道路总长最短，并且每个城市都被连接？

(1) Prim算法  [邻接矩阵]

Prim算法是贪心算法，贪心策略为：找到目前情况下能连上的权值最小的边的另一端点，加入之，直到所有的顶点加入完毕。

Prim适用于稠密图。

朴素Prim的时间复杂度是O(n2)，因为在寻找离生成树最近的未加入顶点时浪费了很多时间。所以，可以用堆进行优化。堆优化后的Prim算法的时间复杂度为O(mlogn)。

堆优化Prim的代码比较复杂，并查集优化的Kruskal算法与它相比，要好很多。

int minEdge[N], cloest[N];    // 与点N连接的最小边 int Prim(int start=0)     // start的出度不能为0！ {  int ans=0, k=0, min;    // 加入第一个点 for (int i=0;i<n;i++) {   minEdge=G[start];   cloest=start; } minEdge[start]=0;   for (int i=0;i<n-1;i++) {   min=INF;    // 寻找离生成树最近的未加入顶点k   for (int j=0;j<n;j++)    if (minEdge[j]!=0 && minEdge[j]<min) min=minEdge[k=j];     // 把找到的边加入到MST中   ans+=minEdge[k];   minEdge[k]=0;    // 加入完毕。以后不用再处理这个点。   // 重新计算最短边   for (int j=0;j<n;j++)    if (G[k][j]<minEdge[j])    {     minEdge[j]=G[k][j];     cloest[j]=k; }

}

return ans;

}

(2) Kruskal算法!  [边目录]

Kruskal算法是贪心算法，贪心策略为：选目前情况下能连上的权值最小的边，若与以生成的树不够成环，加入之，直到n-1条边加入完毕。

时间复杂度为O(nlogm)，最差情况为O(mlogn)。相比于Prim，这个算法更常用。

int parent[N], rank[M];           // p代表并查集，r是边的序号 int comp (const int i, const int j) {return w<w[j];} // 排序时使用 int find (int x)             // 带路径压缩的查找函数 {  return parent[x]==x ? x : parent[x] = find(parent[x]); }  int Kruskal() {  int ans = 0;  for (int i=0;i<n;i++) parent=i;  // 初始化并查集  for (int i=0;i<m;i++) rank=i;   // 边的序号（下面要按照边的权值大小来排序）  sort(rank, rank+m, comp);     // 按照边的权值大小排序   for (int i=0;i<m;i++) {   int e=rank;   int x=find(u[e]), y=find(v[e]);  // 找出当前边的两个端点所在集合的编号   if (x!=y)         // 如果不在同一集合，合并   {    ans += w[e];    parent[x] = y;   } } return ans; }