👉最小生成树👈
连通图：在无向图中，若从顶点 v1 到顶点 v2 有路径（直接相连或间接相连），则称顶点 v1 与顶点 v2 是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图。
生成树：一个连通图的最小连通子图称作该图的生成树。有 n 个顶点的连通图的生成树有 n 个顶点和 n - 1 条边。
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。
若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n - 1 条边。因此构造最小生成树的准则有三条：
只能使用图中权值最小的边来构造最小生成树
只能使用恰好 n - 1 条边来连接图中的 n 个顶点
选用的 n - 1 条边不能构成回路
构成最小生成树的的边的权值和是最小的
构造最小生成树的方法：Kruskal 算法和 Prim 算法。这两个算法都采用了逐步求解的贪心策略。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体。最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。
Kruskal算法
任给一个有 n 个顶点的连通网络 N = {V,E}，首先构造一个由这 n 个顶点组成、不含任何边的图 G = {V,NULL}，其中每个顶点自成一个连通分量，其次不断从 E 中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到 G 中。如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。选边的过程需要判断构不构成回路，可以通过并查集来判断。
Kruskal 算法的实现思路：用优先级队列（小堆）存储图所有的边（注：需要为优先级队列定制一个表示边的类），然后选出 n - 1 条边，选边的时候需要通过并查集（并查集的代码可在之前博客查询）来判断当前选的边是否和之前所选的边构成回路。如果是，那么这条边不能选；如果不是，则可以选这条边。当选出 n - 1 条边，即可返回最小生成树的权值；若循环结束，则说明该图没有最小生成树，返回权值的默认值。
namespace matrix { class Graph { typedef Graph<V, W, W_MAX, Direction> Self; // ... public: Graph() = default; // 强制生成默认构造函数 // 注：src和dst是顶点,srci和dsti是顶点下标 // 因为找出最小生成树的过程只知道顶点的下标,所以需要增加一个通过顶点下标来构造边的子函数 void AddEdge(const V& src, const V& dst, const W& w) { size_t srci = GetVertexIndex(src); size_t dsti = GetVertexIndex(dst); _AddEdge(srci, dsti, w); } void _AddEdge(size_t srci, size_t dsti, const W& w) { _matrix[srci][dsti] = w; // 无向图 if (Direction == false) _matrix[dsti][srci] = w; } struct Edge { size_t _srci; size_t _dsti; W _w; Edge(size_t srci, size_t dsti, const W& w) : _srci(srci) , _dsti(dsti) , _w(w) {} bool operator>(const Edge& eg) const { return _w > eg._w; } }; // 注：只有无向图才有最小生成树 W Kruskal(Self& minTree) { size_t 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, W_MAX); } // 优先级队列默认是小堆(greater),因为比较的是边的权值,所以需要传第三模板类型参数 priority_queue<Edge, vector<Edge>, greater<Edge>> minQueue; for (size_t i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (_matrix[i][j] != W_MAX) { minQueue.push(Edge(i, j, _matrix[i][j])); } } } // 选出n-1条边 size_t size = 0; W total = W(); UnionFindSet ufs(n); while (!minQueue.empty()) { Edge min = minQueue.top(); minQueue.pop(); // 不在一个集合中表示不构成回路 if (!ufs.Inset(min._srci, min._dsti)) { // 查看所选的边 cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; minTree._AddEdge(min._srci, min._dsti, min._w); ufs.Union(min._srci, min._dsti); ++size; total += min._w; // 选出n-1条边了 if (size == n - 1) return total; } else { cout << "构成环的边:"; cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; } } // 该图没有最小生成树 return W(); } } void GraphMinTreeTest1() { 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 << endl; kminTree.Print(); } }
注：图的最小生成树是不唯一的。
Prim算法
namespace matrix { class Graph { typedef Graph<V, W, W_MAX, Direction> Self; // ... public: W Prim(Self& minTree, const V& src) { size_t 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, W_MAX); } // 使用vector来表示集合X和集合Y,可以达到 // O(1)时间复杂度来判断点在不在集合里 // 也可以使用set来表示,但该场景下没有vector高效 size_t srci = GetVertexIndex(src); 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>> minQueue; // 先把srci连接的边添加到队列中 for (size_t i = 0; i < n; ++i) { if (_matrix[srci][i] != W_MAX) minQueue.push(Edge(srci, i, _matrix[srci][i])); } // 选出n-1条边 size_t size = 0; W total = W(); while (!minQueue.empty()) { Edge min = minQueue.top(); minQueue.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; total += min._w; // 已经选出n-1条边 if (size == n - 1) return total; for (size_t i = 0; i < n; ++i) { // i与dsti相连且i不在集合Y中则边_matrix[min._dsti][i]添加进 // 最小生成树中不会构成回路 // 注:判断条件不加Y[i]也行,因为在上面也会判断是否构成回路 // 不过加上Y[i]的效率较高一些 if (_matrix[min._dsti][i] != W_MAX && Y[i]) minQueue.push(Edge(min._dsti, i, _matrix[min._dsti][i])); } } } return W(); // 该图不存在最小生成树,返回默认值 } } }
下方的代码可以得到不同起点的 Prim 算法得到的最小生成树
for (size_t i = 0; i < strlen(str); ++i) { cout << "Prim:" << g.Prim(pminTree, str[i]) << endl; }
