[数据结构]图krusakl算法实现

---

Kruskal算法

我们要在连通图中去找生成树
连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图。

生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。也就是用最少的边（n-1条边）连通起来。

最小生成树：构成生成树的这些边加起来权值最小，也就是最小的成本让这N个顶点连通，最小生成树不唯一。

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。

若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条：

1. 只能使用图中的权值最小的边来构造最小生成树
2. 只能使用恰好n-1条边来连接图中的n个顶点
3. 选用的n-1条边不能构成回路

构造最小生成树的方法：Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

Kruskal算法和Prim算法求出来的一定是最优解吗？——不一定

因此要选出最小的边，然后进行连接

在这里判定是否成环的关键是并查集

代码实现：

W Kruskal(Self& minTree)
{minTree._vertexs = _vertexs;minTree._indexMap = _indexMap;minTree._matrix.resize(_vertexs.size());for (auto& e : minTree._matrix){e.resize(_vertexs.size(), MAX_W);}// 先根据边的权值进行排序priority_queue<Edge, vector<Edge>, greater<Edge>> pq;for (size_t i = 0; i < _vertexs.size(); ++i){for (size_t j = 0; j < _vertexs.size(); ++j){if (i < j && _matrix[i][j] != MAX_W){// pq.push(_matrix[i][j]); 不是这样pq.push(Edge(i, j, _matrix[i][j]));}}}W total = W();size_t i = 1; // 最初有一个顶点// 从最小的边开始进行选择（贪心）UnionFindSet ufs(_vertexs.size());while (i < _vertexs.size() && !pq.empty()){Edge min = pq.top();pq.pop();// 判断是否会构成一个回路，不会则添加到最小生成树中if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti)){cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;minTree._AddEdge(min._srci, min._dsti, min._w);total += min._w;ufs.Union(min._srci, min._dsti);++i;}}if (i == _vertexs.size()){return total;}else{return W();}
}

完整代码：

namespace matrix // 领接矩阵存储
{template <class V, class W, W MAX_W = INT_MAX, bool Direction = false> // Vertex, Weight, Direction表示有向图还是无向图class Graph{typedef Graph<V, W, MAX_W, Direction> Self; // 表示子图public:Graph(){}Graph(const V* vertex, size_t n){_vertexs.reserve(n);for (size_t i = 0; i < n; ++i){_vertexs.push_back(vertex[i]);_indexMap[vertex[i]] = i; // map<V, int>second存的是对应的编号}_matrix.resize(n);for (int i = 0; i < n; ++i){_matrix[i].resize(n, MAX_W);}}size_t GetVertexIndex(const V& v){auto ret = _indexMap.find(v);if (ret != _indexMap.end()){return ret->second;}else{assert(false);return -1;}}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;}}void Print(){// 顶点for (size_t i = 0; i < _vertexs.size(); ++i){cout << "[" << i << "]" << "->" << _vertexs[i] << endl;}cout << endl;// 矩阵// 横下标cout << "  ";for (size_t i = 0; i < _vertexs.size(); ++i){//cout << i << " ";printf("%4d", i);}cout << endl;for (size_t i = 0; i < _matrix.size(); ++i){cout << i << " "; // 竖下标for (size_t j = 0; j < _matrix[i].size(); ++j){//cout << _matrix[i][j] << " ";if (_matrix[i][j] == MAX_W){//cout << "* ";printf("%4c", '*');}else{//cout << _matrix[i][j] << " ";printf("%4d", _matrix[i][j]);}}cout << endl;}cout << endl;}void BFS(const V& src){size_t srci = GetVertexIndex(src);// 队列和标记数组queue<int> q;vector<bool> visited(_vertexs.size(), false); // 标记数组int levelSize = 1; // 保证一层 一层的打印q.push(srci);visited[srci] = true;size_t n = _vertexs.size();while (!q.empty()){for (int i = 0; i < levelSize; ++i){int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << " ";// 把front顶点的邻接顶点入队列for (size_t i = 0; i < n; ++i){if (_matrix[front][i] != MAX_W) // 不是无穷大就是相连的{if (visited[i] == false){q.push(i);visited[i] = true;}}}}cout << endl;levelSize = q.size(); // 下一层的数据个数}cout << endl;}void _DFS(size_t srci, vector<bool> visited){cout << srci << ":" << _vertexs[srci] << endl;visited[srci] = true;// 找srci相邻的没有访问过的点，深度遍历for (size_t i = 0; i < _vertexs.size(); ++i){if (_matrix[srci][i] != MAX_W && visited[i] = false){_DFS(i, visited);}}}void DFS(const V& src){size_t srci = GetVertexIndex(src);vector<bool> visited(_vertexs.size(), false);_DFS(srci, visited);}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& e) const{return _w > e._w;}};W Kruskal(Self& minTree){minTree._vertexs = _vertexs;minTree._indexMap = _indexMap;minTree._matrix.resize(_vertexs.size());for (auto& e : minTree._matrix){e.resize(_vertexs.size(), MAX_W);}// 先根据边的权值进行排序priority_queue<Edge, vector<Edge>, greater<Edge>> pq;for (size_t i = 0; i < _vertexs.size(); ++i){for (size_t j = 0; j < _vertexs.size(); ++j){if (i < j && _matrix[i][j] != MAX_W){// pq.push(_matrix[i][j]); 不是这样pq.push(Edge(i, j, _matrix[i][j]));}}}W total = W();size_t i = 1; // 最初有一个顶点// 从最小的边开始进行选择（贪心）UnionFindSet ufs(_vertexs.size());while (i < _vertexs.size() && !pq.empty()){Edge min = pq.top();pq.pop();// 判断是否会构成一个回路，不会则添加到最小生成树中if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti)){cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;minTree._AddEdge(min._srci, min._dsti, min._w);total += min._w;ufs.Union(min._srci, min._dsti);++i;}}if (i == _vertexs.size()){return total;}else{return W();}}private:vector<V> _vertexs; // 顶点集合map<V, int> _indexMap; // 顶点映射下标vector<vector<W>> _matrix;// 存储边的关系};void TestGraph(){Graph<char, int, INT_MAX, true> g("0123", 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();}void TestBDFS() {string a[] = { "张三", "李四", "王五", "赵六", "周七" };Graph<string, int> g1(a, sizeof(a) / sizeof(string));g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.AddEdge("王五", "周七", 30);g1.Print();g1.BFS("张三");}void TestGraphMinTree(){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();/*Graph<char, int> pminTree;cout << "Prim:" << g.Prim(pminTree, 'a') << endl;pminTree.Print();*/}
}