| kal算法
最小生成树直白的讲就是，挑选N－1条不产生回路最短的边。Kruskal算法算是最直接的表达了这个思想——在剩余边中挑选一条最短的边，看是否产生回路，是放弃，不是选定然后重复这个步骤。说起来倒是很简单，做起来就不那么容易了——判断是否产生回路需要并查集，在剩余边中找一条最短的边需要最小堆（并不需要对所有边排序，所以堆是最佳选择）。
Kruskal算法的复杂度是O(eloge)，当e接近N^2时，可以看到这个算法不如O(N^2)的Prim算法，因此，他适合于稀疏图。而作为稀疏图，通常用邻接表来储存比较好。另外，对于邻接矩阵储存的图，Kruskal算法比Prim算法占不到什么便宜（初始还要扫描N^2条“边”）。因此，最好把Kruskal算法放在Link类里面。
template <class name, class dist> int Link<name, dist>::MinSpanTree(MSTedge<dist>* a)
{
MinHeap<MSTedge<dist> > E; int i, j, k, l = 0;
MFSets V(vNum); list<edge>::iterator iter;
for (i = 0; i < vNum; i++)
for (iter = vertices[i].e->begin(); iter != vertices[i].e->end(); iter++)
E.insert(MSTedge<dist>(i, iter->vID, iter->cost));//建立边的堆
for (i = 0; i < eNum && l < vNum; i++)//Kruskal Start
{
j = V.find(E.top().v1); k = V.find(E.top().v2);
if (j != k) { V.merge(j, k); a[l] = E.top(); l++; }
E.pop();
}
return l;
}
下面是堆和并查集的实现
#ifndef Heap_H
#define Heap_H
#include <vector>
using namespace std;
#define minchild(i) (heap[i*2+1]<heap[i*2+2]?i*2+1:i*2+2)
template <class T>
class MinHeap
{
public:
void insert(const T& x) { heap.push_back(x); FilterUp(heap.size()-1); }
const T& top() { return heap[0]; }
void pop() { heap[0] = heap.back(); heap.pop_back(); FilterDown(0); }
private:
void FilterUp(int i)
{
for (int j = (i - 1) / 2; j >= 0 && heap[j] > heap[i]; i = j, j = (i - 1) / 2)
swap(heap[i], heap[j]);
}
void FilterDown(int i)
{
for (int j = minchild(i); j < heap.size() && heap[j] < heap[i]; i = j, j = minchild(i))
swap(heap[i], heap[j]);
}
vector<T> heap;
};
#endif
#ifndef MFSets_H
#define MFSets_H
class MFSets
{
public:
MFSets(int maxsize) : size(maxsize)
{
parent = new int[size + 1];
for (int i = 0; i <= size; i++) parent[i] = -1;
}
~MFSets() { delete []parent; }
void merge(int root1, int root2)//root1!=root2
{
parent[root2] = root1;
}
int find(int n)
{
if (parent[n] < 0) return n;
return find(parent[n]);
}
private:
int size;
int* parent;
};
#endif
Prim算法
如果从顶点入手，就能得到另一种方法。从只含有一个顶点的集合开始，寻找集合外面的顶点到这个集合里的顶点最近的一条边，然后将这个顶点加入集合，修改因为这个顶点的加入而使得集合外面的顶点到集合里的顶点的最短距离产生变化的分量。因为需要对每个顶点扫描，邻接矩阵储存的图是最合适Prim算法的。
template <class name, class dist> int AdjMatrix<name, dist>::MinSpanTree(MSTedge<dist>* a)
{
dist* lowC = new dist[vNum]; int* nearV = new int[vNum];
int i, j, k;
for (i = 0; i < vNum; i++) { lowC[i] = edge[0][i]; nearV[i] = 0; } nearV[0] = -1;
for (k = 0; k < vNum-1; k++)//Prim Start
{
for (i = 1, j = 0; i < vNum; i++)
if |
