最小生成树与判断无向图是否有回路（并查集）
一、最小生成树算法：
（1）Kruskal算法
（a）找出权重最小的边
（b）判断加入该边以后是否会构成回路（并查集），如果不会，将该边加入生成树中
重复（a）（b），直到生成树中有n-1条边
（2）Prim算法
选一个结点作为起始结点，并将其加入已选结点集合；
（a）寻找与已选结点集合任一 一个（不能是两个）结点相关联的最小边（也就是这条最小边关联的结点不能都在已选结点集合中，从而保证了加入这条边一定不会构成回路）
重复（a）直到生成树中有n-1条边
注意：该算法不用使用并查集判断是否有回路，因为加入的最小边关联的结点不能都在已选结点集合中
代码实现：（Prim算法，可AC练习题目，可优化（参考下面算法2练习题目1的代码））20191206
#include
#define inf 999999
using namespace std;
int book[310],e[301][310],n,count;
int maxm = -inf;
int Prim(int cur){
book[cur] = 1;
count++;
int minn = inf;
int index;
int node;
for(int j=1;j<=n;j++){
if(book[j]==1){
for(int i=1;i<=n;i++){
if(book[i]==0 && e[j][i] minn = e[j][i]; node = j; index = i;//find the smallest distance of two vertices } } } } if(e[node][index]>maxm) maxm = e[node][index]; return index; } int main(){ int i,j,m,a,b,c; cin>>n>>m; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(i==j) e[i][j]=0; else e[i][j]=inf; } } for(i=1;i<=m;i++){ cin>>a>>b>>c; e[a][b]=c; e[b][a]=c;//indirected graph } int next = Prim(1); while(count!=n-1){ //count used to judge if all vertices are in the tree next = Prim(next); } cout< return 0; } 二、用Kruskal判断无向图是否有回路的方法总结： 算法1：并查集（推荐） 并查集（与路径压缩）算法描述：《算法笔记》P328-332 并查集是一种维护集合的数据结构，基础操作如下 初始化：每个元素都是独立的一个集合 查找：反复寻找父亲结点，直到找到根节点 合并：将一个集合的根节点的父亲指向另一个结合的根节点 路径压缩 把当前查询结点的路径上的所有结点的父亲都指向根节点 目的是为了降低查找的时间复杂度 因此带有路径压缩的合并操作步骤如下：以合并ab两个结点为例 查找a结点的根结点：将查询a结点过程中所遍历到的结点的父亲指向根节点 查找b结点的根结点：同上 将a结点所在子树的根节点的父亲指向b结点子树的根节点（理论上是所在树结点少的指向结点多的） 代码实现：（可优化（参考下面算法2练习题目1的代码））20200130 #include #define inf 9999999 using namespace std; int n,edge,maxm; int e[310][310],father[310]; int findfather(int node){ int vertex = node; while(node != father[node]) node = father[node]; while(vertex != father[vertex]){// path compression int temp = vertex; vertex = father[vertex]; father[temp] = node; } return node; } void unionsets(int node1,int node2){ int fa1 = findfather(node1); int fa2 = findfather(node2); father[fa2] = fa1; } bool cycle(int nodea,int nodeb){ if(findfather(nodea) == findfather(nodeb)) return false; else { unionsets(nodea,nodeb); edge++;// end condition return true; } } void Kruskal(){ int minn = inf; int nodea,nodeb; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(e[i][j] < minn) { minn = e[i][j]; nodea = i; nodeb = j; } } } if(cycle(nodea,nodeb)){ maxm = e[nodea][nodeb]; } e[nodea][nodeb] = inf; e[nodeb][nodea] = inf;//ignore the edge checked } int main(){ int m; cin>>n>>m; for(int i=1;i<=n;i++){ father[i] = i; //initialize for(int j=1;j<=n;j++){ e[i][j]=inf; } } int a,b,c; for(int i=1;i<=m;i++){ cin>>a>>b>>c; e[a][b]=c; e[b][a]=c;//indirected } while(edge cout< return 0; } View Code 测试数据：见练习题目第1个 算法2：基于dfs判断（同有向图） 算法描述：拓扑排序与判断有向图是否有环 区别于有向图的是：用dfs判断无向图是否有回路要注意防止结点“杀回马枪”，也就是说要防止结点访问它的父亲结点；比如说1dfs到2，要防止2dfs时去访问1. 解决办法就是记录每一个结点的父亲结点。 代码实现： 练习题目2：20200129 #include #define inf 99999999 using namespace std; int book[110],e[110][110],n,sum,father[110],arr[110][110]; int base = inf; bool dfs (int cur){ book[cur] = -1; for(int i=1;i<=n;i++){ if(e[cur][i]!=0&&e[cur][i]!=inf&&father[cur]!=i&&book[i]==-1) return false; if(e[cur][i]!=0&&e[cur][i]!=inf&&book[i]==0){ father[i] = cur; if(!dfs(i)) return false; } } book[cur] = 1; return true; } bool Kruskal(){ int minn = inf; int nodea,nodeb; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(arr[i][j] minn = arr[i][j]; nodea = i; nodeb = j; } } } if(minn!=inf){ e[nodea][nodeb] = minn; e[nodeb][nodea] = minn; for(int i=0;i<110;i++) book[i] = 0; bool state=1; for(int i=1;i<=n;i++){ base = inf; if(!dfs(i)){ state = 0; break; } } if(!state){ e[nodea][nodeb] = inf; e[nodeb][nodea] = inf; } else sum += minn; arr[nodea][nodeb] = inf; return true; } else return false; } int main(){ cin>>n; int temp; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>temp; if(i==j) temp = inf; arr[i][j] = temp; e[i][j] = inf; } } while(Kruskal()) ; cout< return 0; } View Code 练习题目1：20200131（相对于练习题目2的代码有很大优化） #include #include #define inf 999999 using namespace std; int n,counte,maxm; int book[310],father[310]; bool e[310][310]; typedef struct{ int nodea; int nodeb; int weight; }Edge; Edge edge[100010]; bool cmp(Edge e1,Edge e2){ return e1.weight < e2.weight; } bool dfs (int cur){ book[cur] = -1; for(int i=1;i<=n;i++){ if(e[cur][i]==0) continue; if(e[cur][i]==1 && father[cur]!=i && book[i]==-1) return false; if(e[cur][i]==1 && book[i]==0){ father[i] = cur; if(!dfs(i)) return false; //注意不能单纯地dfs,一定要判断并return false;不判断的话就会执行到最后一行并return true } } book[cur] = 1; return true; } void Kruskal(Edge ed){ e[ed.nodea][ed.nodeb] = 1; e[ed.nodeb][ed.nodea] = 1; for(int i=0;i<310;i++) book[i] = 0;//每放入一条边，都要重新判断是否构成环 bool state=1; for(int i=1;i<=n;i++){ if(book[i] != 0) continue; if(!dfs(i)){ state = 0;//有回路 break; } } if(state){ counte++; maxm = ed.weight; } else{ e[ed.nodea][ed.nodeb] = 0; e[ed.nodeb][ed.nodea] = 0; } } int main(){ int m,a,b,c; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a>>b>>c; edge[i].nodea = a; edge[i].nodeb = b; edge[i].weight = c; } sort(edge,edge+m,cmp); for(int i=1;i<=m;i++) { Kruskal(edge[i]); if(counte == n-1) break; } cout< return 0; } View Code 算法3：如果 边数 + 连通分支数 - 1 >= 结点数，则图中有回路 代码实现：（没有考虑有多个连通分支的情况，第二组测试数据通不过）20191206 #include #define inf 999999 using namespace std; int book[101],e[101][101],n,data[101],sum,count,edge; bool is_cycle(int nodea,int nodeb){ //if edge>=the number of vertices, then there is a cycle int statea=0;//to record if nodea is booked before adding the edge int stateb=0; if(book[nodea]==0){ book[nodea] = 1; count++; statea++; } if(book[nodeb]==0){ book[nodeb] = 1; count++; stateb++; } edge++;//sequence(after count++) //after add the edge, if it leads to a cycle, then recover it if(edge>=count){ edge--; if(statea){ count--; book[nodea]=0; } if(stateb){ count--; book[nodeb]=0; } return true; } else return false; } void Kruskal(){ int minn = inf; int nodea,nodeb; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(e[i][j] minn = e[i][j]; nodea = i; nodeb = j;//find the two vertices of the min edge } } } if(!is_cycle(nodea,nodeb)){ cout< book[nodea] = 1; book[nodeb] = 1; sum += e[nodea][nodeb]; } e[nodea][nodeb] = inf; e[nodeb][nodea] = inf;//ignore the edge checked } int main(){ int i,j,m,a,b,c; scanf("%d %d",&n,&m); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(i==j) e[i][j]=0; else e[i][j]=inf; } } for(i=1;i<=m;i++){ scanf("%d %d %d",&a,&b,&c); e[a][b]=c; e[b][a]=c; } for(int i=0;i cout< return 0; } View Code 测试数据： //左图（AC） 6 9 1 2 10 2 4 5 1 6 2 2 3 3 4 5 11 6 5 3 3 5 15 4 6 10 1 4 20 //右图（WA） 8 8 1 2 1 2 3 2 3 4 3 5 6 4 6 7 5 7 8 6 1 4 7 1 5 8 View Code 练习题目： P2330 [SCOI2005]繁忙的都市 P1546 最短网络 Agri-Net