2023年8月1日发(作者：)

【贪⼼算法】Kruskal算法的实现与应⽤问题背景假设我们有n个位置的集合V={v1, v2, …, vn}，我们想在它们顶部建⽴⼀个通信⽹络，⽹络应该是连通的，即任何两个位置vi和vj之间⾄少存在⼀条路径可以相互到达。对于确定的两个位置(vi,vj)，假设在这两个位置之间建⽴⽹络连接的费⽤为c(i,j)，c(i,j) > 0。将上述问题抽象成⼀个⽆向图G=(V,E)，⽤图来表⽰可能被建⽴的链接的集合，图的每个结点代表每个位置，图的每条边e的长度表⽰该边连接的两个结点vi和vj之间建⽴⽹络连接的费⽤c(i,j)。为了求得最⼩的建造费⽤，只需要找到n-1条边将n个结点连接起来并确保图的连通性，然后这n-1条边的权值尽可能⼩。抽象为图之后上述问题可以⽤最⼩⽣成树模型来解决。算法描述Kruskal算法是⽤于解决最⼩⽣成树问题的⼀种优秀的算法，其主要思路是，先将原图G的所有边按照权值⼤⼩进⾏排序，同时假定我们有⼀个n个结点，但是还没有边的⼦图T。每次都从G的边中取出权值最⼩的边e并尝试加⼊到⼦图T中，加⼊e时需要保持⼦图T中不能产⽣环，如果加⼊e之后会产⽣环则放弃该边，否则把边e加⼊⼦图T。重复这样的操作，直到⼦图T变成⼀个连通图时结束算法，对于⼀个有n个结点的图，等价于在得到n-1条边时就可以结束算法了。Kruskal算法的过程展⽰图如下所⽰：算法实现要实现kruskal算法，先来了解⼀些背景知识，【图的连通分⽀】，⼀个图被分成⼏个⼩块，每个⼩块都是连通的。⼩块与⼩块之间不连通，那么每个⼩块称为⼀个连通分⽀。⼀个孤⽴结点也算⼀个连通分⽀。下⾯，还要需要了解⼀种数据结构，这⾥我暂且将它称为MergeQuery数据结构。在Kruskal算法中，当考虑⼀条边e = (u, v)时，我们需要有效地找出包含结点u和v的连通分⽀。如果两个连通分⽀不同，u和v位于不同的连通分⽀，不存在连接结点u和v的路径，此时边e可以加⼊到最⼩⽣成树中。如果连通分⽀相同，那么u和v处于同⼀个连通分⽀中，也就是已经存在⼀条从u到v路径，此时边e不能加⼊最⼩⽣成树(加⼊的话会产⽣环)。接着，我们在考虑如果⼀条边e连接的结点u和v位于不同的连通分⽀可以加⼊的情况，此时将边e加⼊之后，u和v就连通了，原本u和v所在的两个连通分⽀也将合并称为⼀个连通分⽀。MergeQuery数据结构将⽤于⽀持Kruskal算法的相关操作，该数据结构维护不相交的集合(即图的连通分⽀)，对于⼀个结点u，操作query(u)返回包含u的集合的名字。若query(u) == query(v)则说明u和v位于同⼀连通分⽀。此外还有⼀个操作merge(A, B)，⽤于将两个集合合并为⼀个集合(两个连通分⽀合并)。在Kruskal算法中，选取权值最⼩的边e = (u, v)之后，先使⽤query操作检测u和v是否位于同⼀连通分⽀，若是则放弃这条边，如果不是，则加⼊边e，使⽤merge(A, B)将u和v所在的两个连通分⽀合并。实现MergeQuery的⼀种简单的数据结构：维护⼀个数组component，假设图有n个结点{1, 2, …, n}，创建⼀个长度为n的component数组，初始化component[i] = i。查找操作query(u)可以⽤O(1)的时间给出⼀个结点u所属的集合，合并操作merge(A, B)则需要O(n)的时间来合并两个集合。merge(A, B)的实现如下，任意选择⼀个保留的集合名，⽐如选到A，对于另⼀个集合B中的所有元素i都令component[i]= A。最后，基于kruskal算法的特点，我们存储⼀个图的⽅式将不会使⽤邻接表或者邻接矩阵，⽽是直接存储边，具体的数据结构如下所⽰，重载⼩于操作符的⽬的是为了⽅便对边进⾏排序。struct Edge { Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) { this->vertex1 = vertex1; this->vertex2 = vertex2; this->weight = weight; } int vertex1, vertex2, weight;};bool operator<(const Edge& e1, const Edge& e2) { return < ;}最后，kruskal算法的整个算法流程的伪代码实现如下所⽰：输⼊为n个结点m条边的图，每条边都带有⼀个权值w对所有边按照权值⼤⼩进⾏排序，排序结果为{e1,e2,...,em}初始化MergeQuery数据结构mq，结点数量为nminimalSpanningTree = {};for i=1 to m, do A = (ei.u); B = (ei.v); if A != B (A, B, ei); 将边ei加⼊minimalSpanningTree; endIfendForreturn minimalSpanningTree;整个算法的C++实现如下，下⾯代码运⾏之后会输出⼀个连通图，该图为原图的最⼩⽣成树。同时还会输出最⼩⽣成树所有边的权值的和。#include #include using namespace std;const int MAX_VERTEX_NUM = 10;struct Edge { Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) { this->vertex1 = vertex1; this->vertex2 = vertex2; this->weight = weight; } int vertex1, vertex2, weight;};bool operator<(const Edge& e1, const Edge& e2) { return < ;}class MergeQuery {public: MergeQuery(const int& vertexNum): vertexNum(vertexNum) { component = new int[vertexNum]; for (int i = 0; i < vertexNum; ++i) { for (int i = 0; i < vertexNum; ++i) { component[i] = i; } } ~MergeQuery() { if (component != NULL) delete [] component; } int query(const int& vertex) const { return component[vertex]; } void merge(int A, int B) { for (int i = 0; i < vertexNum; ++i) { if (component[i] == B) component[i] = A; } }private: int vertexNum; int* component;};class Kruskal {public: Kruskal(const int& vertexNum, const int& edgeNum) { this->vertexNum = vertexNum; this->edgeNum = edgeNum; mq = new MergeQuery(vertexNum); edges = new Edge[edgeNum]; minimalSpanningTree = new int[vertexNum-1]; } ~Kruskal() { if (mq != NULL) delete mq; if (edges != NULL) delete [] edges; } void getEdge() { for (int i = 0; i < edgeNum; ++i) { cin >> edges[i].vertex1 >> edges[i].vertex2 >> edges[i].weight; } } void minimalSpanning() { sort(edges, edges + edgeNum); int treeEdgeNum = 0; for (int i = 0; i < edgeNum; ++i) { int A = mq->query(edges[i].vertex1); int B = mq->query(edges[i].vertex2); if (A != B) { mq->merge(A, B); minimalSpanningTree[treeEdgeNum++] = i; } } } void getTree() { int weightSum = 0; cout << "最⼩⽣成树: (v1, v2, weight)" << endl; for (int i = 0; i < vertexNum-1; ++i) { weightSum += edges[minimalSpanningTree[i]].weight; cout << edges[minimalSpanningTree[i]].vertex1 << ' ' << edges[minimalSpanningTree[i]].vertex2 << ' ' << edges[minimalSpanningTree[i]].weight << endl; } cout << "最⼩⽣成树边权值总和为: " << weightSum << endl; }private: int vertexNum; int edgeNum; int* minimalSpanningTree; MergeQuery* mq; Edge* edges;};int main() { int vertexNum, edgeNum; cin >> vertexNum >> edgeNum; if (vertexNum > MAX_VERTEX_NUM) { cout << "结点数量过多" << endl; return -1; } Kruskal k(vertexNum, edgeNum); e(); // 输⼊图的所有边 lSpanning(); // kruskal最⼩⽣成树算法 e(); // 输出结果 return 0;}Kruskal算法的其他应⽤—聚类最⼤间隔聚类：给定集合U = {p1, p2, …, pn}，对于每对个体pi和pj，d(pi, pj)表⽰两个个体之间的距离，规定d(pi, pi)=0，d(pi, pj) > 0(i!= j)，并且d(pi, pj) = d(pj, pi)。给定参数k(k <= n)，将U中的个体划分称为k组，则⼀个U的k聚类是把U分成k个⾮空集合C1, C2, …, Ck的划分。我们希望每个聚类内部的点都尽可能地聚集，密集程度尽可能⾼，⽽位于两个不同聚类中的点尽可能地相互远离，寻找具有最⼤可能间隔的k聚类。在此，我们定义⼀个k聚类的间隔是处在两个不同聚类中的任何⼀对点之间的距离的最⼩值，简单点说就是k个聚类⾥⾯任意两个聚类之间的距离的最⼩值，我们希望这个最⼩值是所有可能的划分中最⼤的，这样，k个聚类就能最⼤程度地远离彼此。最⼤间隔聚类问题可以使⽤kruskal算法来解决。把集合U中的个体看成结点，个体之间的距离看成边，在集合U上⽣成⼀个具有k个连通分⽀的图，这k个连通分⽀就是k个聚类。在⽣成图的过程中都将邻近点尽可能地⼀起带⼊同⼀个聚类中。通过对前⾯kruskal算法的理解我们可以知道，算法开始会初始化n个连通分⽀，然后每次加⼊⼀条边就相当于合并两个连通分⽀，知道最后剩下⼀个连通分⽀时就是最⼩⽣成树了。那，我们把终⽌条件修改⼀下，在使⽤Kruskal最⼩⽣成树算法时，⼀旦得到k个连通分⽀就停⽌算法，由于Kruskal算法每次加⼊新边时都是考虑权值最⼩的边，因此，当得到K个连通分⽀时，还未加⼊的k-1条边中其实就是最⼩⽣成树中距离最⼤的k-1条边，因此，当去掉这最长的k-1条边时得到的这k个聚类的间隔也是最⼤的。若图有n个结点，那么最⼩⽣成树有n-1边，要在加⼊最⼩⽣成树的最后k-1边时结束算法，那么最后得到的k个连通分⽀⼀共有n-k条边，也就是算法在加⼊n-k条边之后即可停⽌了。最后算法的伪代码如下所⽰：输⼊n个结点m条边的图，每条边都带有⼀个权值w对所有边按照权值⼤⼩进⾏排序，排序结果为{e1,e2,...,em}初始化MergeQuery数据结构mq，结点数量为nKCluster = {};edgeNum = 0;for i=1 to m && edgeNum != n-k, do A = (ei.u); B = (ei.v); if A != B (A, B, ei); 将边ei加⼊KCluster; edgeNum = edgeNum + 1; endIfendForreturn KCluster;可以回顾上⾯的kruskal算法流程图，假如我们要聚出3个类，那么在进⾏到(d)这⼀步即可停⽌算法了，此时的3个连通分⽀就是3个最⼤间隔聚类，{v1, v3}，{v2, v5}，{v4, v6}。上述伪代码的C++实现如下，下⾯代码运⾏之后输出结果为⼀个包含k个连通分⽀的图，每个连通分⽀代表⼀个聚类。#include #include using namespace std;const int MAX_VERTEX_NUM = 10;struct Edge { Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) { this->vertex1 = vertex1; this->vertex2 = vertex2; this->weight = weight; } int vertex1, vertex2, weight;};bool operator<(const Edge& e1, const Edge& e2) { return < ;}class MergeQuery {public: MergeQuery(const int& vertexNum): vertexNum(vertexNum) { component = new int[vertexNum]; for (int i = 0; i < vertexNum; ++i) { component[i] = i; } } ~MergeQuery() { if (component != NULL) delete [] component; } int query(const int& vertex) const { return component[vertex]; } void merge(int A, int B) { for (int i = 0; i < vertexNum; ++i) { if (component[i] == B) if (component[i] == B) component[i] = A; } }private: int vertexNum; int* component;};class Kruskal {public: Kruskal(const int& vertexNum, const int& edgeNum, const int& KCluster) { this->vertexNum = vertexNum; this->edgeNum = edgeNum; this->KCluster = KCluster; mq = new MergeQuery(vertexNum); edges = new Edge[edgeNum]; minimalSpanningTree = new int[vertexNum-KCluster]; } ~Kruskal() { if (mq != NULL) delete mq; if (edges != NULL) delete [] edges; } void getEdge() { for (int i = 0; i < edgeNum; ++i) { cin >> edges[i].vertex1 >> edges[i].vertex2 >> edges[i].weight; } } void minimalSpanning() { sort(edges, edges + edgeNum); int treeEdgeNum = 0; for (int i = 0; i < edgeNum && treeEdgeNum < vertexNum-KCluster; ++i) { int A = mq->query(edges[i].vertex1); int B = mq->query(edges[i].vertex2); if (A != B) { mq->merge(A, B); minimalSpanningTree[treeEdgeNum++] = i; } } } void getTree() { int weightSum = 0; cout << "K聚类-结果图: (v1, v2, weight)" << endl; for (int i = 0; i < vertexNum-KCluster; ++i) { cout << edges[minimalSpanningTree[i]].vertex1 << ' ' << edges[minimalSpanningTree[i]].vertex2 << ' ' << edges[minimalSpanningTree[i]].weight << endl; } }private: int vertexNum; int edgeNum; int KCluster; int* minimalSpanningTree; MergeQuery* mq; Edge* edges;};int main() { int vertexNum, edgeNum, KCluster; cin >> vertexNum >> edgeNum >> KCluster; if (vertexNum > MAX_VERTEX_NUM) { cout << "结点数量过多" << endl; return -1; return -1; } if (KCluster > vertexNum) { cout << "聚类数量过⼤，超过结点数量" << endl; return -1; } Kruskal k(vertexNum, edgeNum, KCluster); e(); // 输⼊边 lSpanning(); // kruskal最⼩⽣成树算法 e(); // 输出结果 return 0;}

2023年8月1日发(作者：)

【贪⼼算法】Kruskal算法的实现与应⽤问题背景假设我们有n个位置的集合V={v1, v2, …, vn}，我们想在它们顶部建⽴⼀个通信⽹络，⽹络应该是连通的，即任何两个位置vi和vj之间⾄少存在⼀条路径可以相互到达。对于确定的两个位置(vi,vj)，假设在这两个位置之间建⽴⽹络连接的费⽤为c(i,j)，c(i,j) > 0。将上述问题抽象成⼀个⽆向图G=(V,E)，⽤图来表⽰可能被建⽴的链接的集合，图的每个结点代表每个位置，图的每条边e的长度表⽰该边连接的两个结点vi和vj之间建⽴⽹络连接的费⽤c(i,j)。为了求得最⼩的建造费⽤，只需要找到n-1条边将n个结点连接起来并确保图的连通性，然后这n-1条边的权值尽可能⼩。抽象为图之后上述问题可以⽤最⼩⽣成树模型来解决。算法描述Kruskal算法是⽤于解决最⼩⽣成树问题的⼀种优秀的算法，其主要思路是，先将原图G的所有边按照权值⼤⼩进⾏排序，同时假定我们有⼀个n个结点，但是还没有边的⼦图T。每次都从G的边中取出权值最⼩的边e并尝试加⼊到⼦图T中，加⼊e时需要保持⼦图T中不能产⽣环，如果加⼊e之后会产⽣环则放弃该边，否则把边e加⼊⼦图T。重复这样的操作，直到⼦图T变成⼀个连通图时结束算法，对于⼀个有n个结点的图，等价于在得到n-1条边时就可以结束算法了。Kruskal算法的过程展⽰图如下所⽰：算法实现要实现kruskal算法，先来了解⼀些背景知识，【图的连通分⽀】，⼀个图被分成⼏个⼩块，每个⼩块都是连通的。⼩块与⼩块之间不连通，那么每个⼩块称为⼀个连通分⽀。⼀个孤⽴结点也算⼀个连通分⽀。下⾯，还要需要了解⼀种数据结构，这⾥我暂且将它称为MergeQuery数据结构。在Kruskal算法中，当考虑⼀条边e = (u, v)时，我们需要有效地找出包含结点u和v的连通分⽀。如果两个连通分⽀不同，u和v位于不同的连通分⽀，不存在连接结点u和v的路径，此时边e可以加⼊到最⼩⽣成树中。如果连通分⽀相同，那么u和v处于同⼀个连通分⽀中，也就是已经存在⼀条从u到v路径，此时边e不能加⼊最⼩⽣成树(加⼊的话会产⽣环)。接着，我们在考虑如果⼀条边e连接的结点u和v位于不同的连通分⽀可以加⼊的情况，此时将边e加⼊之后，u和v就连通了，原本u和v所在的两个连通分⽀也将合并称为⼀个连通分⽀。MergeQuery数据结构将⽤于⽀持Kruskal算法的相关操作，该数据结构维护不相交的集合(即图的连通分⽀)，对于⼀个结点u，操作query(u)返回包含u的集合的名字。若query(u) == query(v)则说明u和v位于同⼀连通分⽀。此外还有⼀个操作merge(A, B)，⽤于将两个集合合并为⼀个集合(两个连通分⽀合并)。在Kruskal算法中，选取权值最⼩的边e = (u, v)之后，先使⽤query操作检测u和v是否位于同⼀连通分⽀，若是则放弃这条边，如果不是，则加⼊边e，使⽤merge(A, B)将u和v所在的两个连通分⽀合并。实现MergeQuery的⼀种简单的数据结构：维护⼀个数组component，假设图有n个结点{1, 2, …, n}，创建⼀个长度为n的component数组，初始化component[i] = i。查找操作query(u)可以⽤O(1)的时间给出⼀个结点u所属的集合，合并操作merge(A, B)则需要O(n)的时间来合并两个集合。merge(A, B)的实现如下，任意选择⼀个保留的集合名，⽐如选到A，对于另⼀个集合B中的所有元素i都令component[i]= A。最后，基于kruskal算法的特点，我们存储⼀个图的⽅式将不会使⽤邻接表或者邻接矩阵，⽽是直接存储边，具体的数据结构如下所⽰，重载⼩于操作符的⽬的是为了⽅便对边进⾏排序。struct Edge { Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) { this->vertex1 = vertex1; this->vertex2 = vertex2; this->weight = weight; } int vertex1, vertex2, weight;};bool operator<(const Edge& e1, const Edge& e2) { return < ;}最后，kruskal算法的整个算法流程的伪代码实现如下所⽰：输⼊为n个结点m条边的图，每条边都带有⼀个权值w对所有边按照权值⼤⼩进⾏排序，排序结果为{e1,e2,...,em}初始化MergeQuery数据结构mq，结点数量为nminimalSpanningTree = {};for i=1 to m, do A = (ei.u); B = (ei.v); if A != B (A, B, ei); 将边ei加⼊minimalSpanningTree; endIfendForreturn minimalSpanningTree;整个算法的C++实现如下，下⾯代码运⾏之后会输出⼀个连通图，该图为原图的最⼩⽣成树。同时还会输出最⼩⽣成树所有边的权值的和。#include #include using namespace std;const int MAX_VERTEX_NUM = 10;struct Edge { Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) { this->vertex1 = vertex1; this->vertex2 = vertex2; this->weight = weight; } int vertex1, vertex2, weight;};bool operator<(const Edge& e1, const Edge& e2) { return < ;}class MergeQuery {public: MergeQuery(const int& vertexNum): vertexNum(vertexNum) { component = new int[vertexNum]; for (int i = 0; i < vertexNum; ++i) { for (int i = 0; i < vertexNum; ++i) { component[i] = i; } } ~MergeQuery() { if (component != NULL) delete [] component; } int query(const int& vertex) const { return component[vertex]; } void merge(int A, int B) { for (int i = 0; i < vertexNum; ++i) { if (component[i] == B) component[i] = A; } }private: int vertexNum; int* component;};class Kruskal {public: Kruskal(const int& vertexNum, const int& edgeNum) { this->vertexNum = vertexNum; this->edgeNum = edgeNum; mq = new MergeQuery(vertexNum); edges = new Edge[edgeNum]; minimalSpanningTree = new int[vertexNum-1]; } ~Kruskal() { if (mq != NULL) delete mq; if (edges != NULL) delete [] edges; } void getEdge() { for (int i = 0; i < edgeNum; ++i) { cin >> edges[i].vertex1 >> edges[i].vertex2 >> edges[i].weight; } } void minimalSpanning() { sort(edges, edges + edgeNum); int treeEdgeNum = 0; for (int i = 0; i < edgeNum; ++i) { int A = mq->query(edges[i].vertex1); int B = mq->query(edges[i].vertex2); if (A != B) { mq->merge(A, B); minimalSpanningTree[treeEdgeNum++] = i; } } } void getTree() { int weightSum = 0; cout << "最⼩⽣成树: (v1, v2, weight)" << endl; for (int i = 0; i < vertexNum-1; ++i) { weightSum += edges[minimalSpanningTree[i]].weight; cout << edges[minimalSpanningTree[i]].vertex1 << ' ' << edges[minimalSpanningTree[i]].vertex2 << ' ' << edges[minimalSpanningTree[i]].weight << endl; } cout << "最⼩⽣成树边权值总和为: " << weightSum << endl; }private: int vertexNum; int edgeNum; int* minimalSpanningTree; MergeQuery* mq; Edge* edges;};int main() { int vertexNum, edgeNum; cin >> vertexNum >> edgeNum; if (vertexNum > MAX_VERTEX_NUM) { cout << "结点数量过多" << endl; return -1; } Kruskal k(vertexNum, edgeNum); e(); // 输⼊图的所有边 lSpanning(); // kruskal最⼩⽣成树算法 e(); // 输出结果 return 0;}Kruskal算法的其他应⽤—聚类最⼤间隔聚类：给定集合U = {p1, p2, …, pn}，对于每对个体pi和pj，d(pi, pj)表⽰两个个体之间的距离，规定d(pi, pi)=0，d(pi, pj) > 0(i!= j)，并且d(pi, pj) = d(pj, pi)。给定参数k(k <= n)，将U中的个体划分称为k组，则⼀个U的k聚类是把U分成k个⾮空集合C1, C2, …, Ck的划分。我们希望每个聚类内部的点都尽可能地聚集，密集程度尽可能⾼，⽽位于两个不同聚类中的点尽可能地相互远离，寻找具有最⼤可能间隔的k聚类。在此，我们定义⼀个k聚类的间隔是处在两个不同聚类中的任何⼀对点之间的距离的最⼩值，简单点说就是k个聚类⾥⾯任意两个聚类之间的距离的最⼩值，我们希望这个最⼩值是所有可能的划分中最⼤的，这样，k个聚类就能最⼤程度地远离彼此。最⼤间隔聚类问题可以使⽤kruskal算法来解决。把集合U中的个体看成结点，个体之间的距离看成边，在集合U上⽣成⼀个具有k个连通分⽀的图，这k个连通分⽀就是k个聚类。在⽣成图的过程中都将邻近点尽可能地⼀起带⼊同⼀个聚类中。通过对前⾯kruskal算法的理解我们可以知道，算法开始会初始化n个连通分⽀，然后每次加⼊⼀条边就相当于合并两个连通分⽀，知道最后剩下⼀个连通分⽀时就是最⼩⽣成树了。那，我们把终⽌条件修改⼀下，在使⽤Kruskal最⼩⽣成树算法时，⼀旦得到k个连通分⽀就停⽌算法，由于Kruskal算法每次加⼊新边时都是考虑权值最⼩的边，因此，当得到K个连通分⽀时，还未加⼊的k-1条边中其实就是最⼩⽣成树中距离最⼤的k-1条边，因此，当去掉这最长的k-1条边时得到的这k个聚类的间隔也是最⼤的。若图有n个结点，那么最⼩⽣成树有n-1边，要在加⼊最⼩⽣成树的最后k-1边时结束算法，那么最后得到的k个连通分⽀⼀共有n-k条边，也就是算法在加⼊n-k条边之后即可停⽌了。最后算法的伪代码如下所⽰：输⼊n个结点m条边的图，每条边都带有⼀个权值w对所有边按照权值⼤⼩进⾏排序，排序结果为{e1,e2,...,em}初始化MergeQuery数据结构mq，结点数量为nKCluster = {};edgeNum = 0;for i=1 to m && edgeNum != n-k, do A = (ei.u); B = (ei.v); if A != B (A, B, ei); 将边ei加⼊KCluster; edgeNum = edgeNum + 1; endIfendForreturn KCluster;可以回顾上⾯的kruskal算法流程图，假如我们要聚出3个类，那么在进⾏到(d)这⼀步即可停⽌算法了，此时的3个连通分⽀就是3个最⼤间隔聚类，{v1, v3}，{v2, v5}，{v4, v6}。上述伪代码的C++实现如下，下⾯代码运⾏之后输出结果为⼀个包含k个连通分⽀的图，每个连通分⽀代表⼀个聚类。#include #include using namespace std;const int MAX_VERTEX_NUM = 10;struct Edge { Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) { this->vertex1 = vertex1; this->vertex2 = vertex2; this->weight = weight; } int vertex1, vertex2, weight;};bool operator<(const Edge& e1, const Edge& e2) { return < ;}class MergeQuery {public: MergeQuery(const int& vertexNum): vertexNum(vertexNum) { component = new int[vertexNum]; for (int i = 0; i < vertexNum; ++i) { component[i] = i; } } ~MergeQuery() { if (component != NULL) delete [] component; } int query(const int& vertex) const { return component[vertex]; } void merge(int A, int B) { for (int i = 0; i < vertexNum; ++i) { if (component[i] == B) if (component[i] == B) component[i] = A; } }private: int vertexNum; int* component;};class Kruskal {public: Kruskal(const int& vertexNum, const int& edgeNum, const int& KCluster) { this->vertexNum = vertexNum; this->edgeNum = edgeNum; this->KCluster = KCluster; mq = new MergeQuery(vertexNum); edges = new Edge[edgeNum]; minimalSpanningTree = new int[vertexNum-KCluster]; } ~Kruskal() { if (mq != NULL) delete mq; if (edges != NULL) delete [] edges; } void getEdge() { for (int i = 0; i < edgeNum; ++i) { cin >> edges[i].vertex1 >> edges[i].vertex2 >> edges[i].weight; } } void minimalSpanning() { sort(edges, edges + edgeNum); int treeEdgeNum = 0; for (int i = 0; i < edgeNum && treeEdgeNum < vertexNum-KCluster; ++i) { int A = mq->query(edges[i].vertex1); int B = mq->query(edges[i].vertex2); if (A != B) { mq->merge(A, B); minimalSpanningTree[treeEdgeNum++] = i; } } } void getTree() { int weightSum = 0; cout << "K聚类-结果图: (v1, v2, weight)" << endl; for (int i = 0; i < vertexNum-KCluster; ++i) { cout << edges[minimalSpanningTree[i]].vertex1 << ' ' << edges[minimalSpanningTree[i]].vertex2 << ' ' << edges[minimalSpanningTree[i]].weight << endl; } }private: int vertexNum; int edgeNum; int KCluster; int* minimalSpanningTree; MergeQuery* mq; Edge* edges;};int main() { int vertexNum, edgeNum, KCluster; cin >> vertexNum >> edgeNum >> KCluster; if (vertexNum > MAX_VERTEX_NUM) { cout << "结点数量过多" << endl; return -1; return -1; } if (KCluster > vertexNum) { cout << "聚类数量过⼤，超过结点数量" << endl; return -1; } Kruskal k(vertexNum, edgeNum, KCluster); e(); // 输⼊边 lSpanning(); // kruskal最⼩⽣成树算法 e(); // 输出结果 return 0;}