边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。
最小生成树（MST）：权值最小的生成树。
生成树和最小生成树的应用：要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。
构造网的最小生成树必须解决下面两个问题：
1、尽可能选取权值小的边，但不能构成回路；
2、选取n－1条恰当的边以连通n个顶点；
MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。
1. prim算法
基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：
在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。
此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。
Prim算法的核心:始终保持TE中的边集构成一棵生成树。
注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。
看了上面一大段文字是不是感觉有点晕啊，为了更好理解我在这里举一个例子，示例如下：
（1）图中有6个顶点v1-v6，每条边的边权值都在图上；在进行prim算法时，我先随意选择一个顶点作为起始点，当然我们一般选择v1作为起始点，好，现在我们设U集合为当前所找到最小生成树里面的顶点，TE集合为所找到的边，现在状态如下：
U={v1}； TE={}；
（2）现在查找一个顶点在U集合中，另一个顶点在V-U集合中的最小权值，如下图，在红线相交的线上找最小值。
通过图中我们可以看到边v1-v3的权值最小为1，那么将v3加入到U集合，（v1，v3）加入到TE，状态如下：
U={v1，v3}； TE={（v1，v3）}；
（3）继续寻找，现在状态为U={v1，v3}； TE={（v1，v3）}；在与红线相交的边上查找最小值。
我们可以找到最小的权值为（v3，v6）=4，那么我们将v6加入到U集合，并将最小边加入到TE集合，那么加入后状态如下：
U={v1，v3，v6}； TE={（v1，v3），（v3，v6）}； 如此循环一下直到找到所有顶点为止。
（4）下图像我们展示了全部的查找过程：
2.prim算法程序设计
（1）由于最小生成树包含每个顶点，那么顶点的选中与否就可以直接用一个数组来标记used[max_vertexes];（我们这里直接使用程序代码中的变量定义，这样也易于理解）；当选中一个数组的时候那么就标记，现在就有一个问题，怎么来选择最小权值边，注意这里最小权值边是有限制的，边的一个顶点一定在已选顶点中，另一个顶点当然就是在未选顶点集合中了。我最初的一个想法就是穷搜了，就是在一个集合中选择一个顶点，来查找到另一个集合中的最小值，这样虽然很易于理解，但是很明显效率不是很高，在严蔚敏的《数据结构》上提供了一种比较好的方法来解决：设置两个辅助数组lowcost[max_vertexes]和closeset[max_vertexes]，lowcost[max_vertexes]数组记录从U到V－U具有最小代价的边。对于每个顶点v∈V－U,closedge[v], closeset[max_vertexes]记录了该边依附的在U中的顶点。
注意：我们在考虑两个顶点无关联的时候设为一个infinity 1000000最大值。
说了这么多，感觉有点罗嗦，还是发扬原来的风格举一个例子来说明，示例如下：
过程如下表：顶点标号都比图中的小1，比如v1为0，v2为1，这里首先选择v1点。
|
Lowcost[0] |
Lowcost[1] |
Lowcost[2] |
Lowcost[3] |
Lowcost[4] |
Lowcost[5] |
U |
V-U |
|
|
closeset |
v1，infinity |
v1，6 |
v1，1 |
v1，5 |
v1，infinity |
v1，infinity |
v1 |
v1,v2,v3,v4,v5,v6 |
从这个表格可以看到依附到v1顶点的v3的Lowcost最小为1，那么选择v3，选择了之后我们必须要更新Lowcost数组的值，因为记录从U到V－U具有最小代价的边，加入之后就会改变。这里更新Lowcost和更新closeset数组可能有点难理解，
for (k=;k<vcount;k++)
if (!used[k]&&(G[j][k]<lowcost[k]))
{ lowcost[k]=G[j][k];
closeset[k]=j; }
}
j为我们已经选出来的顶点，如果G[j][k]<lowcost[k]，则意味着最小权值边发生变化，更新该顶点的最小lowcost权值，依附的顶点肯定就是刚刚选出的顶点j，closeset[k]=j。
|
Lowcost[0] |
Lowcost[1] |
Lowcost[2] |
Lowcost[3] |
Lowcost[4] |
Lowcost[5] |
U |
V-U |
|
|
closeset |
v1，infinity |
v1，6 |
v1，1 |
v1，5 |
v3，6 |
v3，4 |
v1，v3 |
v1,v2,v4,v5,v6 |
这样一直选择下去直到选出所有的顶点。
（2）上面把查找最小权值的边结束了，但是这里有一个问题，就是我们没有存储找到的边，如果要求你输出找到的边那么这个程序就需要改进了，我们刚开始的时候选取的是v1作为第一个选择的顶点，那我们设置一个father[]数组来记录每个节点的父节点，当然v1的父节点肯定没有，那么我们设置一个结束标志为-1，每次找到一个新的节点就将它的父节点设置为他依附的节点，这样就可以准确的记录边得存储了。
语法：prim(Graph G,int vcount,int father[]);
参数：
G: 图，用邻接矩阵表示
vcount：表示图的顶点个数
father[]：用来记录每个节点的父节点
返回值：null
注意：
常数max_vertexes为图最大节点数
常数infinity为无穷大
数组存储从0开始
如果下面的源程序有错请参照测试程序。
#define infinity 1000000
#define max_vertexes 5 typedef int Graph[max_vertexes][max_vertexes]; void prim(Graph G,int vcount,int father[])
{
int i,j,k;
int lowcost[max_vertexes];
int closeset[max_vertexes],used[max_vertexes];
int min;
for (i=;i<vcount;i++)
{
/* 最短距离初始化为其他节点到1号节点的距离 */
lowcost[i]=G[][i];
/* 标记所有节点的依附点皆为默认的1号节点 */ closeset[i]=;
used[i]=;
father[i]=-;
}
used[]=; /*第一个节点是在U集合里的*/
/* vcount个节点至少需要vcount-1条边构成最小生成树 */
for (i=;i<=vcount-;i++)
{
j=;
min = infinity;
/* 找满足条件的最小权值边的节点k */
for (k=;k<vcount;k++)
/* 边权值较小且不在生成树中 */
if ((!used[k])&&(lowcost[k]<min))
{
min = lowcost[k];
j=k;
}
father[j]=closeset[j];
used[j]=;;//把第j个顶点并入了U中
for (k=;k<vcount;k++)
/* 发现更小的权值 */
if (!used[k]&&(G[j][k]<lowcost[k]))
{
lowcost[k]=G[j][k];/*更新最小权值*/
closeset[k]=j;;/*记录新的依附点*/
}
}
}
测试程序：
测试用例：
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
5 6 6
4 6 2
#include <stdio.h>
#include <string.h>
#include <stdlib.h> #define infinity 1000000
#define max_vertexes 6
typedef int Graph[max_vertexes][max_vertexes];
void prim(Graph G,int vcount,int father[])
{
int i,j,k;
int lowcost[max_vertexes];
int closeset[max_vertexes],used[max_vertexes];
int min;
for (i=;i<vcount;i++)
{
/* 最短距离初始化为其他节点到1号节点的距离 */
lowcost[i]=G[][i];
/* 标记所有节点的依附点皆为默认的1号节点 */
closeset[i]=;
used[i]=;
father[i]=-;
}
used[]=; /*第一个节点是在s集合里的*/
/* vcount个节点至少需要vcount-1条边构成最小生成树 */
for (i=;i<=vcount-;i++)
{
j=;
min = infinity;
/* 找满足条件的最小权值边的节点k */
for (k=;k<vcount;k++)
/* 边权值较小且不在生成树中 */
if ((!used[k])&&(lowcost[k]<min))
{
min = lowcost[k];
j=k;
}
father[j]=closeset[j];
printf("%d %d\n",j+,closeset[j]+);//打印边
used[j]=;;//把第j个顶点并入了U中
for (k=;k<vcount;k++)
/* 发现更小的权值 */
if (!used[k]&&(G[j][k]<lowcost[k]))
{
lowcost[k]=G[j][k];/*更新最小权值*/
closeset[k]=j;;/*记录新的依附点*/
}
}
} int main()
{
FILE *fr;
int i,j,weight;
Graph G;
int fatheer[max_vertexes];
for(i=; i<max_vertexes; i++)
for(j=; j<max_vertexes; j++)
G[i][j] = infinity;
fr = fopen("prim.txt","r");
if(!fr)
{
printf("fopen failed\n");
exit();
}
while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF)
{
G[i-][j-] = weight;
G[j-][i-] = weight;
} prim(G,max_vertexes,fatheer);
return ; }
程序结果：
3 1
6 3
4 6
2 3
5 2
请按任意键继续. . .
克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程可以用一个图来表示。这里的图的选择借用了Wikipedia上的那个。非常清晰且直观。
首先第一步，我们有一张图，有若干点和边
如下图所示：
第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择。
排序完成后，我们率先选择了边AD。 这样我们的图就变成了
第二步，在剩下的变中寻找。我们找到了CE。这里边的权重也是5
依次类推我们找到了6,7,7。完成之后，图变成了这个样子。
下一步就是关键了。下面选择那条边呢？ BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB, BA, AD, DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里的连通线用红色表示了）。所以最后就剩下EG和FG了。当然我们选择了EG。 最后成功的图就是下图：
到这里所有的边点都已经连通了，一个最小生成树构建完成。
如果要简要得描述这个算法的话就是，首先边的权重排序。（从小到大）循环的判断是否需要选择这里的边。判断的依据则是边的两个顶点是否已经连通，如果连通则继续下一条。不连通就选择使其连通。这个流程还是非常清晰明了。
但是在实现的时候，困难的地方在于如何描述2个点已然连通？ 这里用到了并查集做辅助，至于并查集可以到这里去看看。
这里贴出并查集的代码和Kruscal的C++实现：
/*
*
* Disjoint_Set_Forest.h -- an implementation for disjoint set data structure
*
* Created by Ge Chunyuan on 04/09/2009.
*
* version: 0.1
*/
#pragma once
#ifndef _DISJOINT_SET_H_
#define _DISJOINT_SET_H_
#include <vector>
template <typename T> class DisjointSet
{
public:
DisjointSet();
~DisjointSet();
void makeSet ( const std::vector<T>& s );
bool findSet ( const T& s, T& parent);
void Union ( const T& s1, const T& s2 );
protected:
struct Node
{
int rank;
T data;
Node* parent;
};
int m_nElementCnt;
int m_nSetCnt;
std::vector<Node*> m_Nodes;
};
template< class T> DisjointSet<T>::DisjointSet()
{
m_nElementCnt = ;
m_nSetCnt = ;
}
template< class T> DisjointSet<T>::~DisjointSet()
{
for (int i=;i<m_nElementCnt;i++)
delete m_Nodes[i];
}
template< class T> void DisjointSet<T>::makeSet( const std::vector<T>& s )
{
m_nElementCnt += (int)s.size();
m_nSetCnt += (int)s.size();
std::vector<T>::const_iterator it = s.begin();
for (;it != s.end(); ++ it)
{
Node* pNode = new Node;
pNode->data = *it;
pNode->parent = NULL;
pNode->rank = ;
m_Nodes.push_back(pNode);
}
}
template< class T> bool DisjointSet<T>::findSet( const T& s, T& parent)
{ Node* curNode = NULL;
bool find =false;
for (int i=;i<(int)m_Nodes.size();i++)
{
curNode = m_Nodes[i];
if (curNode->data == s)
{
find = true;
break;
}
} if (!find) return false; // find the root
Node* pRoot = curNode;
while (pRoot->parent != NULL)
{
pRoot = pRoot->parent;
} // update all curNode's parent to root
while (curNode != pRoot)
{
Node* pNext = curNode->parent;
curNode->parent = pRoot;
curNode = pNext;
}
parent = pRoot->data;
return true;
}
template< class T> void DisjointSet<T>::Union( const T& s1, const T& s2 )
{
Node* pNode1 = NULL;
Node* pNode2 = NULL;
int find = ;
for (int i=;i<(int)m_Nodes.size();++i)
{
if (m_Nodes[i]->data == s1 || m_Nodes[i]->data == s2 )
{
find ++;
if (m_Nodes[i]->data == s1)
pNode1 = m_Nodes[i];
else
pNode2 = m_Nodes[i];
}
}
// not found
if ( find != ) return ; if (pNode1->rank > pNode2->rank)
pNode2->parent = pNode1;
else if (pNode1->rank < pNode2->rank)
pNode1->parent = pNode2;
else
{
pNode2->parent = pNode1;
++ pNode1->rank;
}
--m_nSetCnt;
}
#endif //_DISJOINT_SET_H_
// Kruscal_Algorithm.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include "Disjoint_Set_Forest.h"
struct Vertex
{
Vertex () { }
Vertex (std::string n)
{
name = n;
} bool operator==(const Vertex& rhs)
{
return name == rhs.name;
}
bool operator!=(const Vertex& rhs)
{
return name != rhs.name;
}
std::string name;
};
struct Edge
{
Edge () {}
Edge (Vertex v1, Vertex v2, int w)
{
this->v1 = v1;
this->v2 = v2;
this->w = w;
} Vertex v1;
Vertex v2;
int w;
};
struct EdgeSort
{
bool operator()(const Edge& e1, const Edge& e2)
{
return e1.w<e2.w;
}
};
struct PrintEdge
{
void operator() (Edge e)
{
std::cout<< "edge start from "<<e.v1.name <<" to "<<e.v2.name << " with length = "<<e.w <<std::endl;;
}
};
class Graph
{
public:
void appendVertex ( const Vertex& v1)
{
m_vertexs.push_back(v1);
} void appendEdge ( const Vertex& v1, const Vertex& v2, int w)
{
m_edges.push_back( Edge(v1,v2,w) );
}
void minimumSpanningKruskal ()
{
std::vector<Edge> result;
std::sort (m_edges.begin(), m_edges.end(), EdgeSort()); DisjointSet<Vertex> dv;
dv.makeSet(m_vertexs);
std::vector<Edge>::iterator it = m_edges.begin();
for (;it!= m_edges.end();++it)
{
Vertex p1;
Vertex p2;
bool b1 = dv.findSet(it->v1, p1 );
bool b2 = dv.findSet(it->v2, p2 );
if ( b1&& b2 && (p1 != p2))
{
dv.Union(p1, p2);
result.push_back(*it);
}
}
for_each(result.begin(), result.end(), PrintEdge());
}
protected:
std::vector<Vertex> m_vertexs;
std::vector<Edge> m_edges;
};
int _tmain(int argc, _TCHAR* argv[])
{
Graph gr;
Vertex a("A");
Vertex b("B");
Vertex c("C");
Vertex d("D");
Vertex e("E");
Vertex f("F");
Vertex g("G"); gr.appendVertex(a);
gr.appendVertex(b);
gr.appendVertex(c);
gr.appendVertex(d);
gr.appendVertex(e);
gr.appendVertex(f);
gr.appendVertex(g); gr.appendEdge(a,b,);
gr.appendEdge(a,d,);
gr.appendEdge(b,c,);
gr.appendEdge(b,d,);
gr.appendEdge(b,e,);
gr.appendEdge(c,e,);
gr.appendEdge(d,e,);
gr.appendEdge(d,f,);
gr.appendEdge(e,f,);
gr.appendEdge(e,g,);
gr.appendEdge(f,g,);
gr.minimumSpanningKruskal();
system("pause");
return ;
}