<span style="font-family: 微软雅黑; widows: auto; background-color: inherit;">摘要：</span>
本文按照如下顺序进行：
1.介绍最小生成树的概念；
2.介绍prim算法的思想，以及C++实现；
3.介绍并查集概念，给出C++并查集的代码实现（因为kruskal算法必须用到并查集，所以在这里讨论一下）；
4.介绍kruskal算法思想，以及C++实现
5.附录给出prim算法、并查集和kruskal算法实现完整代码和测试程序。
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。（百度百科）
举例说明：图1是一个无向图G，图2是无向图G的最小生成树。
图1图2
说明
：为了简化问题，我们不讨论有多个连通分量的图。
算法思想
举个好玩的例子来理解prim算法的思想：
恶魔prim总会随机降临到一张无向连通图的一个顶点上，并且迅速吞并这个顶点。恶魔试被他吞并的节点都是他的领地，恶魔总是“贪心地”选择离他最近的领地先征服，直到他征服整个大陆。
OKay,我们看一下prim算法的C++代码（完整的代码和单元测试程序我在附录中给出）：
template<class T,class edgeType>
void Graph<T,edgeType>::prim() {
VertexNodeType *nodeTmp = m_vertexNodeSet.front();
if (!nodeTmp) {
//cout<<"No Node exist in this Graph."<<endl;
return ;
}
nodeTmp->setDis(0);
nodeTmp->setKnown();
#ifdef _DEBUG_
cout<<"Node's key = "<<nodeTmp->getVertex()->getKey();
cout<<",Distence = "<<nodeTmp->getVertex()->getDis()<<endl;
#endif
// For_each node.
for (; ;) {
edgeType* edgeTmp = nodeTmp->getAdj();
// For_each adj node.
while (edgeTmp) {
T * Vtmp = edgeTmp->getDes();
#ifdef _DEBUG_
cout<<"Node("<<Vtmp->getKey()<<") "<<endl;;
#endif
if (Vtmp->isknown()) {
edgeTmp = nodeTmp->getNext();
continue;
}
// Update dis.
if (edgeTmp->getWeight() < Vtmp->getDis()) {
Vtmp->setDis((int)edgeTmp->getWeight());
}
edgeTmp = nodeTmp->getNext();
}
// Find the node which has min dis.
nodeTmp = findMindis();
if (!nodeTmp) {
break;
}
nodeTmp->setKnown();
#ifdef _DEBUG_
cout<<"Node's key = "<<nodeTmp->getVertex()->getKey();
cout<<",Distence = "<<nodeTmp->getVertex()->getDis()<<endl;
#endif
}
return ;
}
概念：
关于并查集写的比较好的两篇文章是：
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <iostream>
using namespace std;
/* 实现一个并查集，可以用于判断网络连通性或者kruskal算法 */
template <class T>
class UnionFind {
int m_size;
std::map<T, int> m_hashMap;
int *m_id;
void initUnionFind(T *array) {
for (int i = 0; i < m_size; i++) {
m_hashMap.insert(std::pair<T, int>(array[i],i));
m_id[i] = i;
}
};
int find(T p) {
int r = m_hashMap[p];
while (m_id[r] != r)
r = m_id[r];
return r;
}
public:
UnionFind(T *array,int size) : m_size(size) {
m_id = (int*)malloc(sizeof(int)*size);
if (!m_id) {cout<<"OOM"<<endl; exit(-1);}
initUnionFind(array);
};
~UnionFind() { if (m_id) { free(m_id); m_id = NULL; } };
// 合并元素p和元素q所在的集合.
void unionT(T p, T q) {
int pId = find(p);
int qId = find(q);
if (pId == qId) { return ;}
for (int i = 0; i < m_size; i++) {
if (m_id[i] == pId) {
m_id[i] = qId;
}
}
};
bool isConnected(T p, T q) {
return find(p) == find(q);
};
};
kruskal算法
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。（百度百科）
算法思想
kruskal算法用一个有趣的故事来比喻
kruskal恶魔觉得prim恶魔那种陆军一步步扩大领地的方式太老套了，kruskal恶魔喜欢是空军，kruskal恶魔总是选择离的最近的两个城市(顶点)占领，kruskal恶魔按照如下策略占领：
1.若选择的边的两个顶点都没被占领，那么占领这两个城市，并把这两个城市视作一个根据地；
2.若选择的边的两个顶点分别在kruskal的两个根据地中，那么把两个根据地合并为一个；
3.若选择的边的两个顶点已经在一个根据地内，则什么都不做，开始新的征服。
kruska算法实现源码
template<class T,class edgeType>
void Graph<T,edgeType>::kruskal() {
// Init
list<edgeType*> edgeSet;// 这里用优先队列效率更高
sortEdge(edgeSet);
list<edgeType*> treeEdgeSet;//最小生成树边集
int vertexArraySize = m_vertexNodeSet.size();
T *vertexArray = (T*)malloc(sizeof(T*)*vertexArraySize);
typename std::list<VertexNodeType*>::iterator iter;
int i = 0;
for (iter = m_vertexNodeSet.begin(); iter != m_vertexNodeSet.end(); ++iter) {
vertexArray[i] = iter->getVertex();
i++;
}
UnionFind<T*> vertexUnion(vertexArray,vertexArraySize);
typename std::list<edgeType*>::iterator it;
for (it = edgeSet.begin(); it != edgeSet.end(); ++it) {
// Find Min dis edge.
edgeType *edgeMin = it->front();it->pop_front();
// Is the ori node and des node in same set?
T *ori = edgeMin->getOri();
T *des = edgeMin->getOri();
// If in same set,Ignore.If not,combain the set and add this edge.
if (vertexUnion.isConnected(ori, des)) {
continue;
} else {
vertexUnion.unionT(ori, des);
treeEdgeSet->push_back(edgeMin);
}
}
#ifdef _DEBUG_
typename std::list<edgeType*>::iterator itera;
for (itera = treeEdgeSet.begin(); itera != treeEdgeSet.end(); itera++) {
cout<<itera->getWeight()<<endl;
}
#endif
// Free vertexArray.
if (vertexArray) {
free(vertexArray);
vertexArray = NULL;
}
return ;
}
附录：
实现源码：
#ifndef ___00_alg_tests__minimal_spanning_tree__
#define ___00_alg_tests__minimal_spanning_tree__
#include <stdio.h>
#include <string.h>
#include <list>
#include <vector>
#include "union_find.h"
#define _DEBUG_
#ifdef _DEBUG_
#include <iostream>
using namespace std;
#endif
#define MAX_DISTENCE 0xfffffff
// Vertex value
template<class T,class keyType = long>
class Vertex {
public:
typedef T valueType;
Vertex(keyType key, T value) : m_key(key), m_value(value) {
m_dis = MAX_DISTENCE;
m_known = false;
m_isVisited = false;
};
~Vertex(){};
int getDis() { return m_dis;};
void setDis(int dis) { m_dis = dis; return ;};
bool isknown() { return m_known;};
keyType getKey() { return m_key;};
void init() { m_known = false; m_isVisited = false;};
void setKnown() { m_known = true; return ;};
bool isVisited() { return m_isVisited;};
void setVisited() { m_isVisited = true; return ;};
private:
keyType m_key; /* 顶点关键字. */
valueType m_value; /* 顶点值. */
int m_dis; /* 距离. */
bool m_known; /* 是否已被遍历(prim算法). */
bool m_isVisited; /* 标识是否被访问过(DFS算法). */
};
// Edge
template<class T,class weightType = int>
class Edge {
public:
typedef T nodeType;
Edge(T *ori, T *des, weightType weight) : \
m_ori(ori), m_des(des), m_weight(weight) { };
~Edge() { };
T *getOri() { return m_ori;};
T *getDes() { return m_des;};
weightType getWeight() { return m_weight;}
bool operator< (const Edge<T,weightType> *M) const {
return m_weight < M->getWeight();
};
private:
nodeType *m_ori; /* 边的起始点. */
nodeType *m_des; /* 边的终止点. */
weightType m_weight; /* 边的权值. */
};
template<class T, class edgeType>
class VertexNode {
public:
typedef T nodeType;
VertexNode(T *node) : m_vertex(node) { m_iter = m_adj.begin();};
~VertexNode() { };
/* 清除算法对顶点的副作用. */
void init() { if (m_vertex){ m_vertex->init(); } return ;};
/* 添加边到图. */
void addEdge(edgeType *edge) { m_adj.push_back(edge);};
/* 获取顶点的临接边. */
edgeType *getAdj() { m_iter = m_adj.begin();return *m_iter;};
/* 获取该顶点的下一条临接边 .*/
edgeType *getNext() { m_iter++; return (m_iter != m_adj.end()) ? *m_iter : NULL;};
/* 获取顶点元素. */
T *getVertex() { return m_vertex;};
/* 标识此顶点是否被访问过(prim算法). */
bool isKnown() { return (m_vertex) ? m_vertex->isknown() : false;};
/* 设置此顶点已经被访问过(prim算法). */
void setKnown() { if (m_vertex) {m_vertex->setKnown();} return ;};
/* 获取距离--prim算法*/
int getDis() { if (m_vertex) { return m_vertex->getDis();} exit(-1);}
/* 设置距离. */
void setDis(int dis) { if (m_vertex) { m_vertex->setDis(dis);} return ;};
/* 标识此顶点是否被访问过(dfs算法). */
bool isVisited() { return (m_vertex) ? m_vertex->isVisited() : false ;};
/* 设置此顶点已经被访问过(dfs算法). */
void setVisited() { if (m_vertex) {m_vertex->setVisited();} return ;};
private:
nodeType *m_vertex; /* 顶点元素 */
std::list<edgeType*> m_adj; /* 顶点的邻接表. */
typename std::list<edgeType*>::iterator m_iter; /* 用于遍历邻接点. */
};
template<class T,class edgeType>
class Graph {
public:
Graph(){};
~Graph(){};
typedef VertexNode<T,edgeType> VertexNodeType;
/* 清除算法对图的副作用. */
void init();
/* Prim算法. */
void prim();
/* 深度优先遍历. */
void dfs(VertexNodeType* src);
/* 向图中增加一个顶点. */
void addNode(VertexNode<T,edgeType> *node) { m_vertexNodeSet.push_back(node);};
void kruskal();
private:
/* 顶点集. */
std::list<VertexNodeType*> m_vertexNodeSet;
/* 找到最短的边集--用于prim算法 */
VertexNodeType* findMindis();
void sortEdge(list<edgeType*> &edgeSet);
};
template<class T,class edgeType>
void Graph<T,edgeType>::init() {
typename std::list<VertexNodeType*>::iterator it;
for (it = m_vertexNodeSet.begin(); it != m_vertexNodeSet.end(); ++it) {
it->init();
}
return ;
}
template<class T,class edgeType>
VertexNode<T,edgeType>* Graph<T,edgeType>::findMindis() {
int min = MAX_DISTENCE;
VertexNodeType* minDisNode = NULL;
// for_each node.
typename std::list<VertexNodeType*>::iterator iter;
for (iter = m_vertexNodeSet.begin(); \
iter != m_vertexNodeSet.end(); ++iter) {
VertexNodeType* tmp = *iter;
if (tmp->isKnown()) {
continue;
}
if (min > tmp->getDis())
{
min = tmp->getDis();
minDisNode = tmp;
}
}
return minDisNode;
}
template<class T,class edgeType>
void Graph<T,edgeType>::prim() {
VertexNodeType *nodeTmp = m_vertexNodeSet.front();
if (!nodeTmp) {
//cout<<"No Node exist in this Graph."<<endl;
return ;
}
nodeTmp->setDis(0);
nodeTmp->setKnown();
#ifdef _DEBUG_
cout<<"Node's key = "<<nodeTmp->getVertex()->getKey();
cout<<",Distence = "<<nodeTmp->getVertex()->getDis()<<endl;
#endif
// For_each node.
for (; ;) {
edgeType* edgeTmp = nodeTmp->getAdj();
// For_each adj node.
while (edgeTmp) {
T * Vtmp = edgeTmp->getDes();
#ifdef _DEBUG_
cout<<"Node("<<Vtmp->getKey()<<") "<<endl;;
#endif
if (Vtmp->isknown()) {
edgeTmp = nodeTmp->getNext();
continue;
}
// Update dis.
if (edgeTmp->getWeight() < Vtmp->getDis()) {
Vtmp->setDis((int)edgeTmp->getWeight());
}
edgeTmp = nodeTmp->getNext();
}
// Find the node which has min dis.
nodeTmp = findMindis();
if (!nodeTmp) {
break;
}
nodeTmp->setKnown();
#ifdef _DEBUG_
cout<<"Node's key = "<<nodeTmp->getVertex()->getKey();
cout<<",Distence = "<<nodeTmp->getVertex()->getDis()<<endl;
#endif
}
return ;
}
template<class T,class edgeType>
void Graph<T,edgeType>::sortEdge(list<edgeType*> &edgeSet) {
typename std::list<VertexNodeType*>::iterator it;
for (it = m_vertexNodeSet.begin(); it != m_vertexNodeSet.end(); ++it) {
edgeType *edgeTmp = it->getAdj();
while (edgeTmp) {
edgeSet->push_back(edgeTmp);
edgeTmp = it->getNext();
}
}
sort(edgeSet.begin(), edgeSet.end(), less<edgeType>());
return ;
}
template<class T,class edgeType>
void Graph<T,edgeType>::kruskal() {
// Init
list<edgeType*> edgeSet;// 这里用优先队列效率更高
sortEdge(edgeSet);
list<edgeType*> treeEdgeSet;//最小生成树边集
int vertexArraySize = m_vertexNodeSet.size();
T *vertexArray = (T*)malloc(sizeof(T*)*vertexArraySize);
typename std::list<VertexNodeType*>::iterator iter;
int i = 0;
for (iter = m_vertexNodeSet.begin(); iter != m_vertexNodeSet.end(); ++iter) {
vertexArray[i] = iter->getVertex();
i++;
}
UnionFind<T*> vertexUnion(vertexArray,vertexArraySize);
typename std::list<edgeType*>::iterator it;
for (it = edgeSet.begin(); it != edgeSet.end(); ++it) {
// Find Min dis edge.
edgeType *edgeMin = it->front();it->pop_front();
// Is the ori node and des node in same set?
T *ori = edgeMin->getOri();
T *des = edgeMin->getOri();
// If in same set,Ignore.If not,combain the set and add this edge.
if (vertexUnion.isConnected(ori, des)) {
continue;
} else {
vertexUnion.unionT(ori, des);
treeEdgeSet->push_back(edgeMin);
}
}
#ifdef _DEBUG_
typename std::list<edgeType*>::iterator itera;
for (itera = treeEdgeSet.begin(); itera != treeEdgeSet.end(); itera++) {
cout<<itera->getWeight()<<endl;
}
#endif
// Free vertexArray.
if (vertexArray) {
free(vertexArray);
vertexArray = NULL;
}
return ;
}
/* 深度优先遍历. */
template<class T,class edgeType>
void Graph<T,edgeType>::dfs(VertexNodeType *src) {
// Set node Visited.
VertexNodeType *V = src;
V->setVisited();
// For each W adj to V.
edgeType *edgeTmp = V->getAdj();
while (edgeTmp) {
T *Vtmp = edgeTmp->getDes();
if (!Vtmp->isKnown()) {
dfs(Vtmp);
}
edgeTmp = V->getNext();
}
return ;
}
int testGraphPrim();
int testGraphKruskal();
#endif /* defined(___00_alg_tests__minimal_spanning_tree__) */
单元测试程序源码：
测试并查集：
#include <string>
#include "union_find.h"
int testUnionFind() {
long array[100];
for (int i = 0; i < 100; ++i) {
array[i] = i;
}
UnionFind<long> U(array,100);
U.unionT(99, 5);
U.unionT(88, 8);
U.unionT(8, 99);
if (U.isConnected(88, 5)) {
cout<<"88 and 5 is connected."<<endl;
} else {
cout<<"88 and 5 is connected."<<endl;
}
return 0;
}
#ifdef _DEBUG_UNION_FIND_
int main(int argc, char const *argv[]) {
testUnionFind();
return 0;
}
#endif
测试prim算法
#include <iostream>
#include "minimal_spanning_tree.h"
using namespace std;
#define WeightV0ToV1 1
typedef Vertex<int,long> Vertex_t;
typedef Edge<Vertex<int,long>,int> Edge_t;
typedef VertexNode< Vertex_t,Edge_t > VertexNode_t;
#define _DEBUG_MINIMALS_TREE_
#ifdef _DEBUG_MINIMALS_TREE_
int testGraphPrim() {
#define InitEdge(ori,des,weight) new Edge_t(V[(ori)], V[(des)], (weight))
// Init vertexs.
Vertex_t *V[7];
VertexNode_t *VN[7];
for (int i = 0; i < 7; i++) {
V[i] = new Vertex_t((long)i,i);
VN[i] = new VertexNode_t(V[i]);
}
// Init edges.
Edge_t *E[24];
E[0] = InitEdge(0,1,2);/* V0-->V1 */
E[1] = InitEdge(1,0,2);/* V1-->V0 */
E[2] = InitEdge(0,3,1);/* V0-->V3 */
E[3] = InitEdge(3,0,1);/* V3-->V0 */
E[4] = InitEdge(1,3,3);/* V1-->V3 */
E[5] = InitEdge(3,1,3);/* V3-->V1 */
E[6] = InitEdge(1,4,10);/* V1-->V4 */
E[7] = InitEdge(4,1,10);/* V4-->V1 */
E[8] = InitEdge(2,0,4);/* V2-->V0 */
E[9] = InitEdge(0,2,4);/* V0-->V2 */
E[10] = InitEdge(2,5,5);/* V2-->V5 */
E[11] = InitEdge(5,2,5);/* V5-->V2 */
E[12] = InitEdge(3,2,2);/* V3-->V2 */
E[13] = InitEdge(2,3,2);/* V2-->V3 */
E[14] = InitEdge(3,4,7);/* V3-->V4 */
E[15] = InitEdge(4,3,7);/* V4-->V3 */
E[16] = InitEdge(3,5,8);/* V3-->V5 */
E[17] = InitEdge(5,3,8);/* V5-->V3 */
E[18] = InitEdge(3,6,4);/* V3-->V6 */
E[19] = InitEdge(6,3,4);/* V6-->V3 */
E[20] = InitEdge(4,6,6);/* V4-->V6 */
E[21] = InitEdge(6,4,6);/* V6-->V4 */
E[22] = InitEdge(6,5,1);/* V6-->V5 */
E[23] = InitEdge(5,6,1);/* V5-->V6 */
// Init Vertex Node.
/* Vertex Node 0 */
VN[0]->addEdge(E[0]);
VN[0]->addEdge(E[2]);
VN[0]->addEdge(E[9]);
/* Vertex Node 1 */
VN[1]->addEdge(E[1]);
VN[1]->addEdge(E[4]);
VN[1]->addEdge(E[6]);
/* Vertex Node 2 */
VN[2]->addEdge(E[8]);
VN[2]->addEdge(E[10]);
VN[2]->addEdge(E[13]);
/* Vertex Node 3 */
VN[3]->addEdge(E[3]);
VN[3]->addEdge(E[5]);
VN[3]->addEdge(E[12]);
VN[3]->addEdge(E[14]);
VN[3]->addEdge(E[16]);
VN[3]->addEdge(E[18]);
/* Vertex Node 4 */
VN[4]->addEdge(E[7]);
VN[4]->addEdge(E[15]);
VN[4]->addEdge(E[20]);
/* Vertex Node 5 */
VN[5]->addEdge(E[11]);
VN[5]->addEdge(E[17]);
VN[5]->addEdge(E[23]);
/* Vertex Node 6 */
VN[6]->addEdge(E[19]);
VN[6]->addEdge(E[21]);
VN[6]->addEdge(E[22]);
// Init G.
Graph<Vertex_t, Edge_t> G;
for (int i = 0; i < 7; i++) {
G.addNode(VN[i]);
}
// Run alg prim()
G.prim();
return 0;
}