具体算法思想和过程实现:
请前往B站,观看Up主 : 懒猫老师 的视频
视频1 : 《懒猫老师-数据结构-(42)最小生成树(Prim算法,普里姆算法,普利姆)》
视频2 : 《懒猫老师数据结构-(43)最小生成树(Prim算法的实现,普里姆算法,普利姆)》
视频1传送门
视频2传送门
附上本人实现的代码:
能成功运行,可能会存在有不足的地方,如果有,敬请指出,并多多指教。
// 用邻接矩阵来作为图的存储结构,用来实现求最小生成树。 #include<iostream> using namespace std; #define MVNum 100 #define Maxlnt 32767 #define OK 1 class AMGraph; class AMGraph { private: char vexs[MVNum]; //定义一个顶点表; int arcs[MVNum][MVNum]; //定义一个邻接矩阵; int vexnum, arcnum; // 定义图的当前点数和边数; public: bool creat_graph(); //图的构造函数; int Locate_vex(char c); //定位函数,确定顶点在顶点表当中的位置; void print(); //将图的顶点表和邻接矩阵都给打印出来。 friend void Prim(AMGraph G); }; //辅助数组中所需要用到的结构体: typedef struct SE { char adjvex; int lowcost; //最小生成树中边所对应的最小权值; }; int AMGraph::Locate_vex(char c) { for (int i = 0; i < vexnum; i++) { if (c == vexs[i]) return i; } return -1; // -1表示顶点不存在顶点表当中; } bool AMGraph::creat_graph() { cout << "请依次输入总顶点数和总边数:" << "\t"; cin >> vexnum >> arcnum; //输入总顶点数和总边数; //1. 完成对所有顶点的信息的输入。 for (int i = 0; i < vexnum; i++) { cout << "请输入第" << i + 1 << "个顶点:" << "\t"; cin >> vexs[i]; } //2.对邻接矩阵进行初始化工作;将各条边的权值置为最大值; //对角线上的元素置为 0, 其它边的元素置为最大,即Maxlnt for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { if (i == j) arcs[i][j] = 0; else arcs[i][j] = Maxlnt; } } //3.完成对邻接矩阵中各条边的赋值; for (int k = 0; k < arcnum; k++) { char v1, v2; int w; cout << "请分别输入第" << k + 1 << "条边的两个顶点和权值:" << "\t"; cin >> v1 >> v2 >> w; int i = Locate_vex(v1); int j = Locate_vex(v2); //将边(v1,v2)和其对称边(v2,v1)的权值都值为w; arcs[i][j] = arcs[j][i] = w; } return OK; } void AMGraph::print() { cout << endl << "顶点表的信息: " << endl; for (int i = 0; i < vexnum; i++) { cout << vexs[i] << " "; } cout << endl; cout << "邻接矩阵的信息:" << endl; for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { if (arcs[i][j] == Maxlnt) cout << "∞" << "\t"; else cout << arcs[i][j] << "\t"; if (j == vexnum - 1) cout << endl; } } } int minEdge(SE* array, int n) { int min = Maxlnt; int mark; for (int i = 0; i < n; i++) { if (array[i].lowcost != 0 && array[i].lowcost < min) { min = array[i].lowcost; mark = i; } } return mark; } void output_SMT(int k, SE* array,char c) { cout << "(" << array[k].adjvex; cout << " , " << c << ")" << "\t" << array[k].lowcost << endl; } void Prim(AMGraph G) { int start, k; char c; SE* shortEdge; shortEdge = new SE[G.vexnum]; //1. 对初始辅助数组进行赋初值; cout << "请输入最小生成树的起点: " << "\t"; cin >> c; start = G.Locate_vex(c); //输入起点在顶点表当中的序号 for (int i = 0; i < G.vexnum; i++) { shortEdge[i].lowcost = G.arcs[start][i]; shortEdge[i].adjvex = G.vexs[start]; } shortEdge[start].lowcost = 0; //将起点加入算法思想当中的U集合当中。 for (int i = 0; i < G.vexnum - 1; i++) { k = minEdge(shortEdge, G.vexnum); //寻找最短边的邻接点的序号; output_SMT(k,shortEdge,G.vexs[k]); //输出最小生成树的路径; shortEdge[k].lowcost = 0; //将该顶点加入到算法思想当中的U集合当中; for (int j = 0; j < G.vexnum; j++) { if (G.arcs[k][j] < shortEdge[j].lowcost) { shortEdge[j].lowcost = G.arcs[k][j]; shortEdge[j].adjvex = G.vexs[k]; } } } delete[]shortEdge; } int main() { int minEdge(SE * array, int n); void output_SMT(int k, SE * array); AMGraph p1; p1.creat_graph(); p1.print(); cout << endl; cout << "最小生成树路径为:" << endl; Prim(p1); return 0; }
一、测试数据:
二、测试结果:
谢谢你的收看!