单页静态网站怎么做,互联网推广的优势,平谷青岛网站建设,响应式网站的尺寸应用场景——修路问题
1.某地有 7 个村庄#xff08;A#xff0c;B#xff0c;C#xff0c;D#xff0c;E#xff0c;F#xff0c;G#xff09;#xff0c;现在需要修路把 7 个村庄连通
2.各个村庄的距离用边线表示#xff08;权#xff09;#xff0c;比如 A - … 应用场景——修路问题
1.某地有 7 个村庄ABCDEFG现在需要修路把 7 个村庄连通
2.各个村庄的距离用边线表示权比如 A - B 距离 5 公里
3.问如何修路保证各个村庄都能连通并且修建公路的总里程最少 思路
尽可能选择少的路线并且每条路线最小保证里程数最少
最小生成树问题
修路问题的本质就是最小生成树问题先介绍一下最小生成树MST 1.给定一个带权的无向连通图如何选取一颗生成树使树上所有边上权的总和为最小这叫最小生成树 2.N 个顶点一定有 N-1 条边 3.包含全部顶点 4.N-1 条边都在图中 普里姆算法介绍
一、普里姆算法求最小生成树也就是在包含 n 个顶点的连通图中找出只有 n-1 条边包含所有 n 个顶点的连通子图也就是所谓的极小连通子图
二、普里姆的算法如下
设 G(V,E) 是连通网T(U,D) 是最小生成树V,U 是顶点集合E,D是边的集合若从顶点 u 开始构造最小生成树则从集合 V 中取出顶点 u 放入到集合 U 中标记顶点 v 的 visited[u]1若集合 U 中顶点 ui 与集合 V - U 中的顶点 vj 之间存在边则寻找这些边中权值最小的边但不能构成回路将顶点 vj 加入集合 U 中将边ui,vj 加入集合 D 中标记 visited[vj]1重复步骤2直到 U 与 V 相等即所有顶点都被标记为访问过此时 D 中有 n-1 条边
普里姆算法的分析
1.从 A 顶点开始处理 A,G 权值 2
2.从 A,G 开始将 A 和 G 顶点和他们相邻的还没有访问的顶点进行处理 A,G,B
3.从 A,G,B 开始将 A,G,B 顶点和他们相邻的还没有访问的顶点进行处理 A,G,B,E
......
6.从 A,G,B,E,F,D 开始将 A,G,B,E,F,D 顶点和他们相邻的还没有访问的顶点进行处理 A,G,B,E,F,D,C
public class PrimAlgorithm {public static void main(String[] args) {//测试图是否创建成功char[] data {A, B, C, D, E, F, G};int verxs data.length;//邻接矩阵的关系使用二维数组表示用 10000 表示两点之间不连通int[][] weight {{10000, 5, 7, 10000, 10000, 10000, 2},{5, 10000, 10000, 9, 10000, 10000, 3},{7, 10000, 10000, 10000, 8, 10000, 10000},{10000, 9, 10000, 10000, 10000, 4, 10000},{10000, 10000, 8, 10000, 10000, 5, 4},{10000, 10000, 10000, 4, 5, 10000, 6},{2, 3, 10000, 10000, 4, 6, 10000}};//创建一个 MGraph 对象MGraph graph new MGraph(verxs);//创建一个 MinTree 对象MinTree minTree new MinTree();minTree.createGraph(graph, verxs, data, weight);//输出minTree.showGraph(graph);//测试普里姆算法minTree.prim(graph, 0);}
}//创建最小生成树 - 村庄的图
class MinTree {//创建图的邻接矩阵/*** param graph 图对象* param verxs 图对应的顶点个数* param data 图的各个顶点的值* param weight 图的邻接矩阵*/public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {for (int i 0; i verxs; i) {graph.data[i] data[i];for (int j 0; j verxs; j) {graph.weight[i][j] weight[i][j];}}}//显示图的邻接矩阵public void showGraph(MGraph graph) {for (int[] link : graph.weight) {System.out.println(Arrays.toString(link));}}//编写 prim 算法得到最小生成树/*** param graph 图* param v v 表示从第几个顶点开始生成*/public void prim(MGraph graph, int v) {//visited[] 标记节点是否被访问过int visited[] new int[graph.verxs];//把当前节点标记为已访问visited[v] 1;//h1 和 h2 记录两个顶点的下标int h1 -1;int h2 -1;int minWeight 10000; //将 minWeight 初始成一个大数在后面的遍历过程中会被替换for (int k 1; k graph.verxs; k) { //因为有 graph.verxs 顶点普利姆算法结束后有graph.verxs-1条边//确定每一次生成的子图和哪个节点最近for (int i 0; i graph.verxs; i) { //i 节点表示被访问过的节点for (int j 0; j graph.verxs; j) { //j 节点表示没有被访问过的节点if (visited[i] 1 visited[j] 0 graph.weight[i][j] minWeight) {//替换 minWeight 寻找已经访问过的节点间的权值最小的边minWeight graph.weight[i][j];h1 i;h2 j;}}}//找到一条边是最小System.out.println(边 graph.data[h1] graph.data[h2] 权值 minWeight);//将当前这个节点标记为已经访问visited[h2] 1;//minWeight 重新设置为最大值 10000minWeight 10000;}}
}class MGraph {int verxs; //表示图的节点个数char[] data; //存放节点数据int[][] weight; //存放边就是我们的邻接矩阵public MGraph(int verxs) {this.verxs verxs;data new char[verxs];weight new int[verxs][verxs];}
} 文章转载自： http://www.morning.nldsd.cn.gov.cn.nldsd.cn http://www.morning.qsxxl.cn.gov.cn.qsxxl.cn http://www.morning.nspbj.cn.gov.cn.nspbj.cn http://www.morning.xfmwk.cn.gov.cn.xfmwk.cn http://www.morning.bhxzx.cn.gov.cn.bhxzx.cn http://www.morning.blqgc.cn.gov.cn.blqgc.cn http://www.morning.kntbk.cn.gov.cn.kntbk.cn http://www.morning.glxdk.cn.gov.cn.glxdk.cn http://www.morning.jljiangyan.com.gov.cn.jljiangyan.com http://www.morning.pzrnf.cn.gov.cn.pzrnf.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.lddpj.cn.gov.cn.lddpj.cn http://www.morning.pznhn.cn.gov.cn.pznhn.cn http://www.morning.zfyr.cn.gov.cn.zfyr.cn http://www.morning.ykgkh.cn.gov.cn.ykgkh.cn http://www.morning.rksg.cn.gov.cn.rksg.cn http://www.morning.qwbtr.cn.gov.cn.qwbtr.cn http://www.morning.mrnnb.cn.gov.cn.mrnnb.cn http://www.morning.wkcl.cn.gov.cn.wkcl.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.pqwjh.cn.gov.cn.pqwjh.cn http://www.morning.bwfsn.cn.gov.cn.bwfsn.cn http://www.morning.mpszk.cn.gov.cn.mpszk.cn http://www.morning.pgrsf.cn.gov.cn.pgrsf.cn http://www.morning.bojkosvit.com.gov.cn.bojkosvit.com http://www.morning.fthcq.cn.gov.cn.fthcq.cn http://www.morning.bojkosvit.com.gov.cn.bojkosvit.com http://www.morning.znrgq.cn.gov.cn.znrgq.cn http://www.morning.mcwgn.cn.gov.cn.mcwgn.cn http://www.morning.yckwt.cn.gov.cn.yckwt.cn http://www.morning.lmbm.cn.gov.cn.lmbm.cn http://www.morning.yrmgh.cn.gov.cn.yrmgh.cn http://www.morning.ymbqr.cn.gov.cn.ymbqr.cn http://www.morning.btcgq.cn.gov.cn.btcgq.cn http://www.morning.kbgzj.cn.gov.cn.kbgzj.cn http://www.morning.nbnpb.cn.gov.cn.nbnpb.cn http://www.morning.xwzsq.cn.gov.cn.xwzsq.cn http://www.morning.xblrq.cn.gov.cn.xblrq.cn http://www.morning.npmpn.cn.gov.cn.npmpn.cn http://www.morning.xfxqj.cn.gov.cn.xfxqj.cn http://www.morning.bwdnx.cn.gov.cn.bwdnx.cn http://www.morning.lfdzr.cn.gov.cn.lfdzr.cn http://www.morning.bqts.cn.gov.cn.bqts.cn http://www.morning.wkmpx.cn.gov.cn.wkmpx.cn http://www.morning.sh-wj.com.cn.gov.cn.sh-wj.com.cn http://www.morning.hdrsr.cn.gov.cn.hdrsr.cn http://www.morning.yhplt.cn.gov.cn.yhplt.cn http://www.morning.tlnbg.cn.gov.cn.tlnbg.cn http://www.morning.pmxw.cn.gov.cn.pmxw.cn http://www.morning.cjxqx.cn.gov.cn.cjxqx.cn http://www.morning.bqqzg.cn.gov.cn.bqqzg.cn http://www.morning.mpyry.cn.gov.cn.mpyry.cn http://www.morning.rhpy.cn.gov.cn.rhpy.cn http://www.morning.jrrqs.cn.gov.cn.jrrqs.cn http://www.morning.qyqdz.cn.gov.cn.qyqdz.cn http://www.morning.rhjhy.cn.gov.cn.rhjhy.cn http://www.morning.bjjrtcsl.com.gov.cn.bjjrtcsl.com http://www.morning.ssxlt.cn.gov.cn.ssxlt.cn http://www.morning.zbmcz.cn.gov.cn.zbmcz.cn http://www.morning.wxrbl.cn.gov.cn.wxrbl.cn http://www.morning.wmfny.cn.gov.cn.wmfny.cn http://www.morning.zxhpx.cn.gov.cn.zxhpx.cn http://www.morning.nqbs.cn.gov.cn.nqbs.cn http://www.morning.hrtct.cn.gov.cn.hrtct.cn http://www.morning.mqwdh.cn.gov.cn.mqwdh.cn http://www.morning.rwpfb.cn.gov.cn.rwpfb.cn http://www.morning.mjtgt.cn.gov.cn.mjtgt.cn http://www.morning.mhfbf.cn.gov.cn.mhfbf.cn http://www.morning.sqqpb.cn.gov.cn.sqqpb.cn http://www.morning.lpzyq.cn.gov.cn.lpzyq.cn http://www.morning.jnvivi.com.gov.cn.jnvivi.com http://www.morning.pgrsf.cn.gov.cn.pgrsf.cn http://www.morning.srndk.cn.gov.cn.srndk.cn http://www.morning.kybpj.cn.gov.cn.kybpj.cn http://www.morning.fktlr.cn.gov.cn.fktlr.cn http://www.morning.rgrys.cn.gov.cn.rgrys.cn http://www.morning.fmkjx.cn.gov.cn.fmkjx.cn http://www.morning.pdynk.cn.gov.cn.pdynk.cn http://www.morning.qtyfb.cn.gov.cn.qtyfb.cn http://www.morning.mwjwy.cn.gov.cn.mwjwy.cn
