图的应用

一、最小生成树 📌什么是生成树? 连通图的生成树是包含图中所有顶点的一个极小连通子图,通俗地讲,就是“边尽可能少,但需保持连通”。 规律: 对于一个顶点数|V|=n的树,其生成树的边数|E|=n-1。如果将|E|+1,必然会形成回路;如果将|E|-1,则会成为非连通图。 📌什么是最小生成树? 最小生成树,也称最小代价树(Minimum Spanning Tree,MST) 是带权连通无向图的生成树中边的权值之和最小的一棵树,联系实际问题不难理解其中“最小代价”的意味。 Prim(普利姆算法),Kruskal(克鲁斯卡尔算法)就是寻找最小生成树的常用算法。 1.Prim(普利姆算法) 从某一顶点开始,每次将代价最小的新顶点纳入生成树,直至所有顶点都纳入为止。 图示 易知,此方法得到的最小生成子树是不唯一的。 代码实现 void MiniSpanTree_PRIMI(Graph G,int u){ //从顶点u出发找G的最小生成树 for (int i = 0; i <G.vexnum; ++i) {//辅助数组初始化 if(i!=u){ closedge[i]={u,G.arcs[u][i]}; } } closedge[u].lowcost=0; for (int j = 0; j < G.vexnum; j++) { k=minimum(closedge);//求生成树的下一个节点 cout<<cloedge[k].adjvex<<G.vex[k]; closedge[k].lowcost=0; for (int i = 0; i < G.vexnum; i++) { if (G.arc[k][j].adj<closedge[j].lowcost) { closedge[j]={G....

Jun 4, 2021 · 3 min · Archai