之前写了prim算法实现最小生成树，接下来看看kruskal算法 对于给定的图G，令其最小生成树T初始时为G到n个顶点(边为0)，然后将G的边上权重从小到大排序，每次选取最小到边，如果选中的边的两个顶点是连通的，则删除该条边，选取下一条边，如果选中的两个顶点不连通，那么该边加入到T中，如此重复，直到所有顶点都连通 看图:
好了，接下来就是画思想为实践了，不妨先定义一个定位权重的函数
//根据权重定位边的两个顶点,值得注意可能有多条边权重相同 void adjaMultiList::locateInfo(double weight, vector<int> &a, vector<int> &b) { for (int i = 0; i < iVertex; ++i) { edgeNode*p = verNode[i].firstEdge; while (p) { if (p->info == weight) { a.push_back(p->aVertex); b.push_back(p->bVertex); } p = p->aLink; } } } void adjaMultiList::kruskalTree() { cout << "最小生成树的各边及权值为:" << endl; /* kruskal算法关键问题是如何判断在选中若干条边后，某两个顶点是否连通，可以根据书上的一种简单的 方法，定义一个一维数组f,开始时每个顶点为一个连通分量，f[i]=i;比如加入边a,b后，可以令f[a]=a[b] 那么以后判断时就可以根据f[a]和f[b]是否相等即可 */ int f[MAXVERTEX]; int u[MAXVERTEX];//u用来保存图的最小生成树的顶点 for (int i = 0; i < iVertex; ++i)//初始时为空 { u[i] = -1; f[i] = i; } int m = 0;//m保存u中顶点个数 int n = 0;//n表示已经选中的边数 vector<double> dEdge;//保存所有边 for (int i = 0;i < iVertex;++i) { edgeNode*p = verNode[i].firstEdge; while (p) { dEdge.push_back(p->info); p = p->aLink; } } sort(dEdge.begin(), dEdge.end());//排序 while(n!=iVertex-1)//如果边数为顶点数-1，则整个图连通 { vector<int> aVec; vector<int> bVec; double weight = *dEdge.begin(); locateInfo(weight, aVec, bVec); for (int i = 0; i < aVec.size(); ++i) { int a = aVec[i]; int b = bVec[i]; if (m == 0)//当u中没有顶点时，肯定可以连,并且增加两个顶点 { cout << "边： " << a<< " " << b << " 权重: " << *dEdge.begin() << endl; m += 2; u[0] = a; u[1] = b; f[a] = f[b]; auto p = dEdge.begin(); dEdge.erase(p); ++n; //continue; } else { int countA = 0; int countB = 0; for (int j = 0; j < m; j++) { if (u[j] == a) ++countA; if (u[j] == b) ++countB; } if (countA&&countB)//如果两个都在u中 { //两个顶点都在u中，且是连通的，那么不能连 if (f[a] == f[b]) { auto p = dEdge.begin(); dEdge.erase(p); } else { cout << "边： " << a << " " << b << " 权重: " << *dEdge.begin() << endl; auto p = dEdge.begin(); dEdge.erase(p); ++n; //这里要注意，将a以及所有与a连通的顶点的f[]值都改为b的，或者反过来 for (int i1 = 0; i1 < iVertex; i1++) { if (f[i1] == f[a]) f[i1] = f[b]; } } continue; } if (!countA && !countB)//两个顶点均不在u中 { m += 2; u[m - 2] = a; u[m - 1] = b; f[a] = f[b]; cout << "边： " << a << " " << b << " 权重: " << *dEdge.begin() << endl; auto p = dEdge.begin(); dEdge.erase(p); ++n; continue; } if (countA + countB == 1)//有一个结点在u中 { cout << "边： " << a << " " << b << " 权重: " << *dEdge.begin() << endl; ++m; if (countA) { u[m - 1] = b; //b不在u中，直接f[b]=f[a]即可 f[b] = f[a]; } else { u[m - 1] = a; //相反 f[a] = f[b]; } auto p = dEdge.begin(); dEdge.erase(p); ++n; continue; } } } } }