1.概念
连通图中的每一棵生成树，都是原图的一个极大无环子图，
即：从其中删去任何一条边，生成树就不在连通；
反之，在其中引入任何一条新边，都会形成一条回路。
2.步骤
若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。
因此构造最小生成树的准则有三条：
-
只能使用图中的边来构造最小生成树
-
只能使用恰好n-1条边来连接图中的n个顶点
-
选用的n-1条边不能构成回路
3.方法
构造最小生成树的方法：Kruskal算法和Prim算法。
这两个算法都采用了逐步求解的贪心策略。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。
也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。
贪心算法不是对所有的问题都能得到整体最优解。
1.Kruskal算法
任给一个有n个顶点的连通网络N={V,E}，
首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量，
其次不断从E中取出权值最小的一条边(若有多条任取其一)，
若该边的两个顶点来自不同的连通分量，则将此边加入到G中。
如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。
实现
W Kruskal(Self& minTree)
{
int n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
if (i < j && _matrix[i][j] != MAX_W)
{
minque.push(Edge(i, j, _matrix[i][j]));
}
}
}
int size = 0;
W totalW = W();
UnionFindSet ufs(n);
while (!minque.empty())
{
Edge min = minque.top();
minque.pop();
if (!ufs.InSet(min._srci, min._dsti))
{
cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << "->" << min._w << endl;
minTree._AddEdge(min._dsti, min._srci, min._w);
ufs.Union(min._srci, min._dsti);
++size;
totalW += min._w;
}
else
{
cout << "构成环:";
cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << "->" << min._w << endl;
}
}
cout << endl;
if (size == n - 1)
{
return totalW;
}
else
{
return W();
}
}
void TestKruskal()
{
const char* str = "abcdefghi";
Graph<char, int> g(str, strlen(str));
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
//g.AddEdge('a', 'h', 9);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);
Graph<char, int> kminTree;
cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
kminTree.Print();
}输出结果：
2.Prim算法
Prim 算法的工作原理与 Dijkstra的最短路径算法相似。
Prim算法所具有的一个性质是集合A中的边总是构成一棵树。
一棵树从一个任意的根结点开始，一直长大到覆盖V中的所有结点时为止。
算法每一步在连接集合A和A之外的结点的所有边中，选择一条轻量级边加入到A中。
这条规则所加入的边都是对A安全的边。
因此，当算法终止时，A中的边形成一棵最小生成树。
本策略也属于贪心策略，因为每步所加入的边都必须是使树的总权重增加量最小的边。
实现：
W Prim(Self& minTree, const W& src)
{
size_t srci = GetVertexIndex(src);
int n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
/*set<int> X;
set<int> Y;
X.insert(srci);
for (size_t i = 0;i < n; i++)
{
if (i != srci)
{
Y.insert(i);
}
}
*/
vector<bool> X(n, false);
vector<bool> Y(n, true);
X[srci] = true;
Y[srci] = false;
//从X->Y集合连接边里面选出最小的边
priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
//先把srci连接的边添加到队列中
for (size_t i = 0; i < n; i++)
{
if (_matrix[srci][i] != MAX_W)
{
minque.push(Edge(srci, i, _matrix[srci][i]));
}
}
cout << "Prim开始选边" << endl;
size_t size = 0;
W totalW = W();
while (!minque.empty())
{
Edge min = minque.top();
minque.pop();
//判环！
//最小边的目标点也在X集合,则构成环
if (X[min._dsti])
{
cout << "构成环的边:";
cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << "->" << min._w << endl;
}
else
{
minTree._AddEdge(min._srci, min._dsti, min._w);
cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << "->" << min._w << endl;
X[min._dsti] = true;
Y[min._dsti] = false;
++size;
totalW += min._w;
if (size == n - 1)
{
break;
}
for (size_t i = 0; i < n; i++)
{
if (_matrix[min._dsti][i] != MAX_W && Y[i])
{
minque.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
}
}
}
}
if (size == n - 1)
{
return totalW;
}
else
{
return W();
}
}
void TestPrim()
{
const char* str = "abcdefghi";
Graph<char, int> g(str, strlen(str));
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
//g.AddEdge('a', 'h', 9);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);
Graph<char, int> pminTree;
cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
pminTree.Print();
cout << endl;
for (size_t i = 0; i < strlen(str); i++)
{
cout << "Prim:" << g.Prim(pminTree, str[i]) << endl;
cout << endl;
}
}输出结果：
