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

最⼩⽣成树-Kruskal算法详解（含全部代码）⽬录适⽤条件加权连通图（可以判定图是否连通）测试所⽤图与所⽤图相同，就是课本上的。算法步骤1.对边按权重排序为e1、e2、...2.若已选择V-1条边，停⽌。否则，按边的权重排序选择下⼀条边。3.判断选择的边的两点是否在同⼀连通分⽀。若不在同⼀分⽀，则选择该边。返回步骤2。Kruskal算法代码//最⼩⽣成树-Kruskal算法void Kruskal(Graph G){ //初始化 sort((), (),cmp); int verSet[MaxVerNum]; int mincost = 0; for (int i = 0; i < ; i++) verSet[i] = i; cout << "最⼩⽣成树所有边:" << endl; //依次查看边 int all = 0; for (int i = 0; i < ; i++) { if (all == - 1)break; int v1 = verSet[l[i].from]; int v2 = verSet[l[i].to]; //该边连接两个连通分⽀ if (v1 != v2) { cout << "(" << l[i].from << "," << l[i].to << ") "; mincost += l[i].weight; //合并连通分⽀ for (int j = 0; j < ; j++) { if (verSet[j] == v2)verSet[j] = v1; } all++; } } cout << "最⼩⽣成树权值之和:" <#include#include#include#include#include#include#include#include#include#include#include#include#define MaxVerNum 100 //顶点最⼤数⽬值#define VexType char //顶点数据类型#define EdgeType int //边数据类型,⽆向图时邻接矩阵对称，有权值时表⽰权值，没有时1连0不连#define INF 0x3f3f3f3f//作为最⼤值using namespace std;//图的数据结构typedef struct Graph{ VexType Vex[MaxVerNum];//顶点表 EdgeType Edge[MaxVerNum][MaxVerNum];//边表 int vexnum, arcnum;//顶点数、边数}Graph;//迪杰斯特拉算法全局变量bool S[MaxVerNum]; //顶点集int D[MaxVerNum]; //到各个顶点的最短路径int Pr[MaxVerNum]; //记录前驱//Prim算法所⽤数据结构typedef struct closedge{ int adjvex; //最⼩边在集合U（最⼩边在当前⼦树顶点集合中的那个顶点的下标） int lowcost; //最⼩边上的权值};//Kruskal算法所⽤数据结构typedef struct Edge{ int from; //起点下标 int to; //终点下标 int weight; //权值};vector l;//按权值⽐较bool cmp(Edge e1, Edge e2){ if (<) if (<) { return true; } return false;}//*********************************************基本操作函数*****************************************////初始化函数 参数：图G 作⽤：初始化图的顶点表，邻接矩阵等void InitGraph(Graph &G){ memset(, '#', sizeof());//初始化顶点表 //初始化边表 for (int i = 0; i < MaxVerNum; i++) for (int j = 0; j < MaxVerNum; j++) { [i][j] = INF; if (i == j)[i][j] = 0;//在最⼩⽣成树时，考虑⽆环简单图,故⾃⼰到⾃⼰设置为0 } = = 0; //初始化顶点数、边数}//插⼊点函数 参数：图G,顶点v 作⽤：在图G中插⼊顶点v,即改变顶点表bool InsertNode(Graph &G, VexType v){ if ( < MaxVerNum) { [++] = v; return true; } return false;}//插⼊边函数 参数：图G,某边两端点v和w 作⽤：在图G两点v,w之间加⼊边，即改变邻接矩阵bool InsertEdge(Graph &G, VexType v, VexType w, int weight){ int p1, p2;//v,w两点下标 p1 = p2 = -1;//初始化 for (int i = 0; i<; i++)//寻找顶点下标 { if ([i] == v)p1 = i; if ([i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//两点均可在图中找到 { [p1][p2] = [p2][p1] = weight;//⽆向图邻接矩阵对称 ++; //Kruskal算法增加代码 Edge e; = p1; = p2; = weight; _back(e); return true; } return false;}//判断是否存在边(v,w)函数 参数：图G，某边两端点v和w 作⽤：判断是否存在边(v,w)

bool Adjancent(Graph G, VexType v, VexType w){ int p1, p2;//v,w两点下标 p1 = p2 = -1;//初始化 for (int i = 0; i<; i++)//寻找顶点下标 { if ([i] == v)p1 = i; if ([i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//两点均可在图中找到 if (-1 != p1&&-1 != p2)//两点均可在图中找到 { if ([p1][p2] == 1)//存在边 { return true; } return false; } return false;}bool visited[MaxVerNum];//访问标记数组，⽤于遍历时的标记//⼴度遍历函数 参数：图G,开始结点下标start 作⽤：宽度遍历void BFS(Graph G, int start){ queue Q;//辅助队列 cout << [start];//访问结点 visited[start] = true; (start);//⼊队 while (!())//队列⾮空 { int v = ();//得到队头元素 ();//出队 for (int j = 0; j<; j++)//邻接点 { if ([v][j] "; cout << [j];//访问结点 visited[j] = true; (j);//⼊队 } } }//while cout << endl;}//深度遍历函数（递归形式）参数：图G,开始结点下标start 作⽤：深度遍历void DFS(Graph G, int start){ cout << [start];//访问 visited[start] = true; for (int j = 0; j < ; j++) { if ([start][j] < INF && !visited[j])//是邻接点且未访问 { cout << "->"; DFS(G, j);//递归深度遍历 } }}//最短路径 - Dijkstra算法 参数：图G、源点vvoid Dijkstra(Graph G, int v){ //初始化 int n = ;//n为图的顶点个数 for (int i = 0; i < n; i++) { S[i] = false; D[i] = [v][i]; if (D[i] < INF)Pr[i] = v; //v与i连接，v为前驱 else Pr[i] = -1; } S[v] = true; D[v] = 0; //初始化结束,求最短路径，并加⼊S集 for (int i = 1; i < n; i++) { { int min = INF; int temp; for (int w = 0; w < n; w++) if (!S[w] && D[w] < min) //某点temp未加⼊s集，且为当前最短路径 { temp = w; min = D[w]; } S[temp] = true; //更新从源点出发⾄其余点的最短路径 通过temp for (int w = 0; w < n; w++) if (!S[w] && D[temp] + [temp][w] < D[w]) { D[w] = D[temp] + [temp][w]; Pr[w] = temp; } }}//输出最短路径void Path(Graph G, int v){ if (Pr[v] == -1) return; Path(G, Pr[v]); cout << [Pr[v]] << "->";}//**********************************************功能实现函数*****************************************////打印图的顶点表void PrintVex(Graph G){ for (int i = 0; i < ; i++) { cout << [i] << " "; } cout << endl;}//打印图的边矩阵void PrintEdge(Graph G){ for (int i = 0; i < ; i++) { for (int j = 0; j < ; j++) { if ([i][j] == INF)cout << "∞ "; else cout << [i][j] << " "; } cout << endl; }}//创建图功能实现函数 参数：图G InsertNode 作⽤：创建图void CreateGraph(Graph &G){ VexType v, w; int vn, an;//顶点数，边数 cout << "请输⼊顶点数⽬:" << endl; cin >> vn; cout << "请输⼊边数⽬:" << endl; cin >> an; cout << "请输⼊所有顶点名称:" << endl; for (int i = 0; i> v; if (InsertNode(G, v)) continue;//插⼊点 else { cout << "输⼊错误！" << endl; break; cout << "输⼊错误！" << endl; break; } } cout << "请输⼊所有边（每⾏输⼊边连接的两个顶点及权值）:" << endl; for (int j = 0; j> v >> w >> weight; if (InsertEdge(G, v, w, weight)) continue;//插⼊边 else { cout << "输⼊错误！" << endl; break; } } PrintVex(G); PrintEdge(G);}//⼴度遍历功能实现函数 参数：图G 作⽤：宽度遍历void BFSTraverse(Graph G){ for (int i = 0; i> vname; for (int i = 0; i < ; i++) if ([i] == vname)v = i; if (v == -1) { cout << "没有找到输⼊点！" << endl; return; } Dijkstra(G, v); cout << "⽬标点" << "t" << "最短路径值" << "t" << "最短路径" << endl; for (int i = 0; i < ; i++) { if (i != v) { cout << " " << [i] << "t" << " " << D[i] << "t"; Path(G, i); cout << [i] << endl; cout << [i] << endl; } }}//最⼩⽣成树-Prim算法 参数：图Gvoid Prim(Graph G){ int v = 0;//初始节点 closedge C[MaxVerNum]; int mincost = 0; //记录最⼩⽣成树的各边权值之和 //初始化 for (int i = 0; i < ; i++) { C[i].adjvex = v; C[i].lowcost = [v][i]; } cout << "最⼩⽣成树的所有边:" << endl; //初始化完毕，开始-1次循环 for (int i = 1; i < ; i++) { int k; int min = INF; //求出与集合U权值最⼩的点 权值为0的代表在集合U中 for (int j = 0; j<; j++) { if (C[j].lowcost != 0 && C[j].lowcost

与Prim算法对⽐对⽐项思想扩展⼦树直⾄包含所有顶点维护⽣成森林直⾄合并为⼀棵树优化适合其他Prim使⽤优先队列稠密图

Kruskal使⽤并查集稀疏图可以判断图是否连通更多数据结构与算法实现：有问题请下⽅评论，转载请注明出处，并附有原⽂链接，谢谢！如有侵权，请及时联系。

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

最⼩⽣成树-Kruskal算法详解（含全部代码）⽬录适⽤条件加权连通图（可以判定图是否连通）测试所⽤图与所⽤图相同，就是课本上的。算法步骤1.对边按权重排序为e1、e2、...2.若已选择V-1条边，停⽌。否则，按边的权重排序选择下⼀条边。3.判断选择的边的两点是否在同⼀连通分⽀。若不在同⼀分⽀，则选择该边。返回步骤2。Kruskal算法代码//最⼩⽣成树-Kruskal算法void Kruskal(Graph G){ //初始化 sort((), (),cmp); int verSet[MaxVerNum]; int mincost = 0; for (int i = 0; i < ; i++) verSet[i] = i; cout << "最⼩⽣成树所有边:" << endl; //依次查看边 int all = 0; for (int i = 0; i < ; i++) { if (all == - 1)break; int v1 = verSet[l[i].from]; int v2 = verSet[l[i].to]; //该边连接两个连通分⽀ if (v1 != v2) { cout << "(" << l[i].from << "," << l[i].to << ") "; mincost += l[i].weight; //合并连通分⽀ for (int j = 0; j < ; j++) { if (verSet[j] == v2)verSet[j] = v1; } all++; } } cout << "最⼩⽣成树权值之和:" <#include#include#include#include#include#include#include#include#include#include#include#include#define MaxVerNum 100 //顶点最⼤数⽬值#define VexType char //顶点数据类型#define EdgeType int //边数据类型,⽆向图时邻接矩阵对称，有权值时表⽰权值，没有时1连0不连#define INF 0x3f3f3f3f//作为最⼤值using namespace std;//图的数据结构typedef struct Graph{ VexType Vex[MaxVerNum];//顶点表 EdgeType Edge[MaxVerNum][MaxVerNum];//边表 int vexnum, arcnum;//顶点数、边数}Graph;//迪杰斯特拉算法全局变量bool S[MaxVerNum]; //顶点集int D[MaxVerNum]; //到各个顶点的最短路径int Pr[MaxVerNum]; //记录前驱//Prim算法所⽤数据结构typedef struct closedge{ int adjvex; //最⼩边在集合U（最⼩边在当前⼦树顶点集合中的那个顶点的下标） int lowcost; //最⼩边上的权值};//Kruskal算法所⽤数据结构typedef struct Edge{ int from; //起点下标 int to; //终点下标 int weight; //权值};vector l;//按权值⽐较bool cmp(Edge e1, Edge e2){ if (<) if (<) { return true; } return false;}//*********************************************基本操作函数*****************************************////初始化函数 参数：图G 作⽤：初始化图的顶点表，邻接矩阵等void InitGraph(Graph &G){ memset(, '#', sizeof());//初始化顶点表 //初始化边表 for (int i = 0; i < MaxVerNum; i++) for (int j = 0; j < MaxVerNum; j++) { [i][j] = INF; if (i == j)[i][j] = 0;//在最⼩⽣成树时，考虑⽆环简单图,故⾃⼰到⾃⼰设置为0 } = = 0; //初始化顶点数、边数}//插⼊点函数 参数：图G,顶点v 作⽤：在图G中插⼊顶点v,即改变顶点表bool InsertNode(Graph &G, VexType v){ if ( < MaxVerNum) { [++] = v; return true; } return false;}//插⼊边函数 参数：图G,某边两端点v和w 作⽤：在图G两点v,w之间加⼊边，即改变邻接矩阵bool InsertEdge(Graph &G, VexType v, VexType w, int weight){ int p1, p2;//v,w两点下标 p1 = p2 = -1;//初始化 for (int i = 0; i<; i++)//寻找顶点下标 { if ([i] == v)p1 = i; if ([i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//两点均可在图中找到 { [p1][p2] = [p2][p1] = weight;//⽆向图邻接矩阵对称 ++; //Kruskal算法增加代码 Edge e; = p1; = p2; = weight; _back(e); return true; } return false;}//判断是否存在边(v,w)函数 参数：图G，某边两端点v和w 作⽤：判断是否存在边(v,w)

bool Adjancent(Graph G, VexType v, VexType w){ int p1, p2;//v,w两点下标 p1 = p2 = -1;//初始化 for (int i = 0; i<; i++)//寻找顶点下标 { if ([i] == v)p1 = i; if ([i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//两点均可在图中找到 if (-1 != p1&&-1 != p2)//两点均可在图中找到 { if ([p1][p2] == 1)//存在边 { return true; } return false; } return false;}bool visited[MaxVerNum];//访问标记数组，⽤于遍历时的标记//⼴度遍历函数 参数：图G,开始结点下标start 作⽤：宽度遍历void BFS(Graph G, int start){ queue Q;//辅助队列 cout << [start];//访问结点 visited[start] = true; (start);//⼊队 while (!())//队列⾮空 { int v = ();//得到队头元素 ();//出队 for (int j = 0; j<; j++)//邻接点 { if ([v][j] "; cout << [j];//访问结点 visited[j] = true; (j);//⼊队 } } }//while cout << endl;}//深度遍历函数（递归形式）参数：图G,开始结点下标start 作⽤：深度遍历void DFS(Graph G, int start){ cout << [start];//访问 visited[start] = true; for (int j = 0; j < ; j++) { if ([start][j] < INF && !visited[j])//是邻接点且未访问 { cout << "->"; DFS(G, j);//递归深度遍历 } }}//最短路径 - Dijkstra算法 参数：图G、源点vvoid Dijkstra(Graph G, int v){ //初始化 int n = ;//n为图的顶点个数 for (int i = 0; i < n; i++) { S[i] = false; D[i] = [v][i]; if (D[i] < INF)Pr[i] = v; //v与i连接，v为前驱 else Pr[i] = -1; } S[v] = true; D[v] = 0; //初始化结束,求最短路径，并加⼊S集 for (int i = 1; i < n; i++) { { int min = INF; int temp; for (int w = 0; w < n; w++) if (!S[w] && D[w] < min) //某点temp未加⼊s集，且为当前最短路径 { temp = w; min = D[w]; } S[temp] = true; //更新从源点出发⾄其余点的最短路径 通过temp for (int w = 0; w < n; w++) if (!S[w] && D[temp] + [temp][w] < D[w]) { D[w] = D[temp] + [temp][w]; Pr[w] = temp; } }}//输出最短路径void Path(Graph G, int v){ if (Pr[v] == -1) return; Path(G, Pr[v]); cout << [Pr[v]] << "->";}//**********************************************功能实现函数*****************************************////打印图的顶点表void PrintVex(Graph G){ for (int i = 0; i < ; i++) { cout << [i] << " "; } cout << endl;}//打印图的边矩阵void PrintEdge(Graph G){ for (int i = 0; i < ; i++) { for (int j = 0; j < ; j++) { if ([i][j] == INF)cout << "∞ "; else cout << [i][j] << " "; } cout << endl; }}//创建图功能实现函数 参数：图G InsertNode 作⽤：创建图void CreateGraph(Graph &G){ VexType v, w; int vn, an;//顶点数，边数 cout << "请输⼊顶点数⽬:" << endl; cin >> vn; cout << "请输⼊边数⽬:" << endl; cin >> an; cout << "请输⼊所有顶点名称:" << endl; for (int i = 0; i> v; if (InsertNode(G, v)) continue;//插⼊点 else { cout << "输⼊错误！" << endl; break; cout << "输⼊错误！" << endl; break; } } cout << "请输⼊所有边（每⾏输⼊边连接的两个顶点及权值）:" << endl; for (int j = 0; j> v >> w >> weight; if (InsertEdge(G, v, w, weight)) continue;//插⼊边 else { cout << "输⼊错误！" << endl; break; } } PrintVex(G); PrintEdge(G);}//⼴度遍历功能实现函数 参数：图G 作⽤：宽度遍历void BFSTraverse(Graph G){ for (int i = 0; i> vname; for (int i = 0; i < ; i++) if ([i] == vname)v = i; if (v == -1) { cout << "没有找到输⼊点！" << endl; return; } Dijkstra(G, v); cout << "⽬标点" << "t" << "最短路径值" << "t" << "最短路径" << endl; for (int i = 0; i < ; i++) { if (i != v) { cout << " " << [i] << "t" << " " << D[i] << "t"; Path(G, i); cout << [i] << endl; cout << [i] << endl; } }}//最⼩⽣成树-Prim算法 参数：图Gvoid Prim(Graph G){ int v = 0;//初始节点 closedge C[MaxVerNum]; int mincost = 0; //记录最⼩⽣成树的各边权值之和 //初始化 for (int i = 0; i < ; i++) { C[i].adjvex = v; C[i].lowcost = [v][i]; } cout << "最⼩⽣成树的所有边:" << endl; //初始化完毕，开始-1次循环 for (int i = 1; i < ; i++) { int k; int min = INF; //求出与集合U权值最⼩的点 权值为0的代表在集合U中 for (int j = 0; j<; j++) { if (C[j].lowcost != 0 && C[j].lowcost

与Prim算法对⽐对⽐项思想扩展⼦树直⾄包含所有顶点维护⽣成森林直⾄合并为⼀棵树优化适合其他Prim使⽤优先队列稠密图

Kruskal使⽤并查集稀疏图可以判断图是否连通更多数据结构与算法实现：有问题请下⽅评论，转载请注明出处，并附有原⽂链接，谢谢！如有侵权，请及时联系。