图的应用——最小生成树

图的应用——最小生成树

​​最小生成树​​

​​求最小生成树​​

​​构造最小生成树的准则​​​​贪心算法(Greedy Algorithm)​​

​​Prim（普里姆）算法​​

​​算法思想 —— 归并顶点​​​​算法设计​​

​​KrusKal（克鲁斯卡尔）算法​​

​​算法思想 —— 归并边​​​​算法设计​​

​​Prim和KrusKal比较​​

最小生成树

求最小生成树

使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。

在网的多个生成树中，寻找一个各边权值之和最小的生成树

构造最小生成树的准则

必须只使用该网中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点不能使用产生回路的边

贪心算法(Greedy Algorithm)

算法原理：以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。算法优点：因为省去了为寻找解而穷尽所有可能所必须耗费的大量时间，因此算法效率高。

贪婪算法的精神就是“只顾如何获得眼前最大的利益”,有时不一定是最优解。

Prim（普里姆）算法

算法思想 —— 归并顶点

算法设计

在算法中需要设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边

struct { VertexType adjvex; // U集中的顶点 VRType lowcost; // 边的权值} closedge[MAX_VERTEX_NUM];

lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MSTadjvext[i]:表示对应lowcost[i]的起点，即说明边是MST的一条边，当adjvex[i]=0表示起点i加入MST

void MiniSpanTree_P(MGraph G, VertexType u){ // 用普利姆算法从顶点u出发构造网G的最小生成树 k = LocateVex_MG(G, u); for(j = 0; j < G.vexnum; ++j) // 辅助数组初始化 if(j != k){ closedge[j].adjvex = new char[10]; strcpy(closedge[j].adjvex, G.vexs[k]); closedge[j].lowcost = G.arcs[k][j].adj; } closedge[k].lowcost = 0; // 初始, U = {u} closedge[k].adjvex = new char[10]; strcpy(closedge[k].adjvex, G.vexs[k]); for(i = 0; i > G.vexnum; i ++){ // //继续向生成树上添加顶点 mincost = INF; // 找权值最小的顶点 for(m = 0; m < G.vexnum; ++m) if(mincose > closedge[m].lowcost && closedge[m].lowcost != 0){ mincose = closedge[m].lowcost; k = m; } // 求出加入生成树的下一个顶点(k) if(closedge[k].lowcost != 0) //输出生成树上一条边 cout << closedge[k].adjvex << G.vexs[k] << closedge[k].lowcost; closedge[k].lowcost = 0; // 第k顶点并入U集 for(j = 0; j < G.vexnum; j++) // 修改其它顶点的最小边 if(G.arcs[k][j].adj < closedge[j].lowcost){ strcpy(closedge[j].adjvex, G.vexs[k]); closedge[j].lowcost = G.arcs[k][j].adj; } }}

KrusKal（克鲁斯卡尔）算法

算法思想 —— 归并边

算法设计

构造非连通图 ST=( V,{ } ); k = i = 0; // k 计选中的边数 while (k

typedef struct { // 增加边结构定义 int beginvex, endvex; // 边的起点、终点 VRType cost; // 边的权值} edgetype;edgetype edges[MAX_VERTEX_NUM];void MiniSpanTree_Kruskal(ALGraph &G){ int parents[MAX_VERTEX_NUM]; cin >> G.vexnum >> G.arcnum; // 顶点数、弧数 for(i = 0; i < G.vexnum; i++){ // 建立顶点表 G.vertices[i].data = new char[10]; cin >> G.vertices[i].data; // 读入顶点信息并初始化 G.vertices[i].firstarc = NULL; } for(k = 0; k < G.arcnum; k++){ // 建立边表 v1 = new char[10]; v2 = new char[10]; cin >> v1 >> v2 >> w; i = LocateVex_ALG(G, v1); j = LocateVex_ALG(G, v2); edges[k].beginvex = i; edges[k].endvex = j; edges[k].cost = w; p = new ArcNode; p->info = NULL; p->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p; } Sort(G, edges); // 按权值大小，对边进行排序 for(i = 0; i < G.vexnum; i++) parents[i] = 0; for(i = 0; i < G.arcnum; i++){ bnf = Find(parents, edges[i].beginvex); // 查找边头分量 edf = Find(parents, edges[i].endvex); // 查找边尾分量 if(bnf != edf){ parents[bnf] = edf; cout << edges[i].beginvex << edges[i].endvex; cout << " " << edges[i].cost << endl; } }}int Find(int parents[], int f){ // 查找函数 while(parents[f] > 0) f = parents[f]; return f;}

Prim和KrusKal比较

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。