其中克鲁斯卡尔算法中判断是否发生自环也可采用DFS和BFS判断，这里采用是并查集
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 100000000;
class Edge
{
public:
int x1,x2;//边的两个顶点
int w;//权
Edge(int X1,int X2, int W):x1(X1),x2(X2),w(W){}
};
bool compare(Edge e1,Edge e2)
{
return e1.w<e2.w;
}
int find_min(int *a,int n)
{
int min=INF;
int minloc=-1;
for(int i=0;i<n;i++)
{
if(a[i]!=0&&min>a[i])
{
min=a[i];
minloc=i;
}
}
return minloc;
}
void print_map(int *a,int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<*(a+i*n+j)<<' ';
}
cout<<endl;
}
cout<<endl;
}
int find(int *a,int x) //并查集，查找当前节点的根节点的下标
{
while(a[x]!=-1)
x=a[x];
return x;
}
class Graph
{
public:
int vexnum; //顶点个数
int** arc; //邻接矩阵
Graph(int num) //初始化，分配内存
{
vexnum=num;
arc=new int* [num];
for(int i=0;i<num;i++) arc[i]=new int[num];
}
void input() //输入
{
for(int i=0;i<vexnum;i++)
for(int j=0;j<vexnum;j++)
cin>>arc[i][j];
}
void Prim() //prim算法
{
int minDistant[vexnum];//生成树内的顶点到各点的最小距离:若为无穷(INF),则为不可到达;若为0,则为该顶点在生成树内
int parent[vexnum];//记录mindistant中的最小距离是由哪个生成树的顶点到该点的距离,若mindistant为INF,则为-1
int current_map[vexnum][vexnum];//当前生成树的邻接矩阵
for(int i=0;i<vexnum;i++)//对上述三个数组进行初始化,mindistant初始为INF,parent为-1，邻接矩阵为0;
{
minDistant[i]=INF;
parent[i]=-1;
for(int j=0;j<vexnum;j++) current_map[i][j]=0;
}
int point=0;
minDistant[0]=0;//从0开始
while(true)
{
print_map((int*)current_map,vexnum);//输出当前邻接矩阵
for(int i=0;i<vexnum;i++)//更新，看新加入的点到其他点是否存在更短的距离
{
if(arc[point][i]!=0&&arc[point][i]<minDistant[i])
{
minDistant[i]=arc[point][i];
parent[i]=point;
}
}
int min_point=find_min(minDistant,vexnum);//找出在mindistant找距离最短的一个点，如果没找到则返回-1。
if(min_point==-1)//-1说明所有顶点已经全在生成树内
break;
current_map[min_point][parent[min_point]]=current_map[parent[min_point]][min_point]=arc[parent[min_point]][min_point];
//将新节点和与距离新节点最短距离的节点(parent v)连接
point=min_point;//记录该最短节点，以此循环将该节点假如生成树内
minDistant[point]=0; //加点，0代表在生成树内
}
}
void Kruskal()
{
vector<Edge> edge; //将所有的边的信息存入数组
bool visited[vexnum];//顶点访问信息
int parent[vexnum];//每个节点对应的父节点，-1为根节点
int current_map[vexnum][vexnum];//当前邻接矩阵
for(int i=0;i<vexnum;i++)//上述数组初始化
{
visited[i]=false;
parent[i]=-1;
for(int j=0;j<vexnum;j++) current_map[i][j]=0;
}
for(int i=0;i<vexnum;i++)//通过邻接矩阵传入边的信息
{
for(int j=i+1;j<vexnum;j++)
{
if(arc[i][j]!=0)
edge.push_back(Edge(i,j,arc[i][j]));
}
}
sort(edge.begin(),edge.end(),compare);//升序排序
for(int i=0;i<edge.size();i++)//遍历每个边的信息
{
int x1=edge[i].x1,x2=edge[i].x2;
if(find(parent,x1)==find(parent,x2)) continue;//若这两个顶点的根节点来自同一个根节点，那么他们不能相连，否则会发生自环；
print_map((int*)current_map,vexnum);//打印当前邻接矩阵，二维数组必须转化成一维数组才能传入
if(visited[x1]==false&&visited[x2]==false) //如果两个节点都未访问过，随便令一个为根，另一个为其子节点
parent[x2]=x1;
else if(visited[x1]==false) //若其中一个访问过，另一个没有，那么让没有访问过的节点为访问过的节点的子节点
parent[x1]=x2;
else if(visited[x2]==false)
parent[x2]=x1;
else //若两个都被访问过，且不同根（不是同一个连通分量），那么将这两个集合合并，即让任意一个的根节点等于另一个的子节点
{
int root1=find(parent,x1);
int root2=find(parent,x2);
parent[root2]=root1;
}
visited[x1]=visited[x2]=true;
current_map[x1][x2]=current_map[x2][x1]=arc[x1][x2];// 更新至当前邻接矩阵
}
print_map((int*)current_map,vexnum);
}
};
int main() {
int n;
cin>>n;
Graph graph(n);
graph.input();
cout<<"Prim:"<<endl;
graph.Prim();
cout<<"Kruskal:"<<endl;
graph.Kruskal();
}
// 64 位输出请用 printf("%lld")