上住房和城乡建设部网站,建网站能上传多少数据,网站描述代码怎么写,糗事百科 wordpress一.引例
在n个城市之间建设通信网络#xff0c;至少需要架设多少条通信线路#xff1f;如果每两个城市之间架设通信线路的造价是不一样的#xff0c;那么如何设计才能使得总造价最小#xff1f; 二.生成树与生成森林
生成树#xff1a;n个顶点的连通图G的生成树是包含G中…一.引例
在n个城市之间建设通信网络至少需要架设多少条通信线路如果每两个城市之间架设通信线路的造价是不一样的那么如何设计才能使得总造价最小 二.生成树与生成森林
生成树n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。
生成森林在非连通图中由每个连通分量都可以得到一颗生成树这些连通分量的生成树就组成了一个非连通图的生成森林。 三.最小生成树Minimal Spanning Tree MST性质
假设GVE是一个无向连通网U是顶点集V的一个非空子集。若uv是一条具有最小权值的边其中u属于Uv属于V-U则必存在一棵包含边uv的最小生成树。 如何利用MST性质寻找最小生成树
找到两个点集之间最小权值的边 如何处理点集使得最小权值的边构成生成树
1从一个点出发依次加入点形成点集Prim
2从边出发将点集合并避免形成环Kruskal 四.Prim算法
1.基本思想
设GVE是具有n个顶点的连通网TUTE是G的最小生成树T的初始状态为U{u0},TE{},重复执行下述操作找一条代价最小的边uv并入合集TE同时v并入U直至UV。 2.代码实现 templateclass T
void Prim(MGraph TG,int start){int i,j,nG.getVertexNum(),k;struct node shortEdge[n];for(i0;in;i){shortEdge[i].lowcostG.arc[start][i];shortEdge[i].adjvexstart;}shortEdge[start].lowcost0;//起点放入集合U中for(i0;in-1;i){kminEdge(shortEdge, n);//寻找最短边的邻接点koutputSMT(k, shortEdge[k]);//输出最小生成树路径shortEdge[k].lowcost0;//将顶点k加入到集合U中for(j0;jn;j){//调整数组shortEdgeif(G.arc[k][j]shortEdge[j].lowcost){shortEdge[j].lowcostG.arc[k][j];shortEdge[j].adjvexk;}}}
}int minEdge(struct node shortEdge[],int n){int i,min0,flag1;for(i0;in;i){if(shortEdge[i].adjvex!0flag){mini;flag0;}else if(shortEdge[i].adjvex!0){if(shortEdge[i].lowcostshortEdge[min].lowcost){mini;}}}return min;
}void outputSMT(int k,struct node shortEdge){cout(shortEdge.adjvex,k)shortEdge.lowcost;
}3.时间复杂度
Prim算法的时间复杂度为On^2与 顶点数有关
