一.问题引入
1.问题引入
1)有胜利乡有7个村庄(A, B,C,D,E,F,G),现在需要修路把7个村庄连通
2)各个村庄的距离用边线表示(权),比如A-B距离5公里
3)问:如何修路保证各个村庄都能连通,并且总的修建公路总里程最短?
2.最小生成树
修路问题本质就是就是最小生成树问题,先介绍一下最小生成树(Minimum Cost Spanning Tree),简称MST.
1) 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为
最小,这叫最小生成树
2)N个顶点,一定有N-1条边
3)包含全部顶点
4)N-1条边都在图.
5)举例说明(如图)
6)求最小生成树的算法主要是普里姆
算法和克鲁斯卡尔算法
二.普利姆算法
1.基本介绍
1)普利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找出只有
(n-1)条边包含所有n个顶点的连通子图,也就是所谓的极小连通子图
2)普利姆的算法如下:
(1)设G=(V,E)是连通网,T=(U,D)是最小生成树,v,u是顶点集合,E,D是边的集合
(2)若从顶点u开始构造最小生成树,则从集合v中取出顶点u放入集合u中,标记顶点v的
visited[u]=1
(3若集合u中顶点ui与集合v-u中的顶点vj之间存在边,则寻找这些边中权值最小的边,但不
能构成回路,将顶点vj加入集合u中,将边(ui,vj〉加入集合D中,标记visited[vj]=1
(4)重复步骤②,直到u与v相等,即所有顶点都被标记为访问过
此时D中有n-1条边
(5)提示:单独看步骤很难理解,我们通过代码来讲解,比较好理解.
2.算法图解
1.从<A>顶点开始处理======><A,G>
A-C[7] A-G[2] A-B[5]
2.<A,G>开始,将A和G顶点和他们相邻的还没有访问的顶点进行处理=====><A,G,B>
A-C[7] A-B[5] G-B[3] G-E[4] G-F[6]
3.<4,G,B>开始,将A,G,B顶点和他们相邻的还没有访问的顶点进行处理====><A,G,B,E>
A-C[7] G-E[4] G-F[6] B-D[9]
4.{A,G,B,E}->F//第4次大循环,对应边<E,F>权值:5
5.{A,G,B,E,F}->D//第5次大循环,对应边<F,D>权值:4
6.{A,G,B,E,F,D}->C//第6次大循环,对应边<A,C>权值:7 ======>{A,G,B,E,F,D,C}
3.代码实现
public class Prim {public static void main(String[] args) {char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};int vertex = data.length;//邻接矩阵的关系用二维数组表示,其中Integer.MAX_VALUE表示不连通int[][] weight = new int[][]{{Integer.MAX_VALUE, 5, 7, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 2},{5, Integer.MAX_VALUE, Integer.MAX_VALUE, 9, Integer.MAX_VALUE, Integer.MAX_VALUE, 3},{7, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 8, Integer.MAX_VALUE, Integer.MAX_VALUE},{Integer.MAX_VALUE, 9, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, Integer.MAX_VALUE},{Integer.MAX_VALUE, Integer.MAX_VALUE, 8, Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 4},{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 5, Integer.MAX_VALUE, 6},{2, 3, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 6, Integer.MAX_VALUE}};MGraph graph = new MGraph(vertex, data, weight);prim(graph, 0);}/*** @param graph 图* @param v表示从图的第几个顶点开始生成*/public static void prim(MGraph graph, int v) {//标记结点是否访问过了,默认false,表示没有访问过boolean[] isVisted = new boolean[graph.vertex];isVisted[v] = true;//index1和index2为两个顶点的下标int index1 = -1, index2 = -1;//将初始最小权重为最大值int minWeight = Integer.MAX_VALUE;for (int k = 1; k < graph.vertex; ++k) {for (int i = 0; i < graph.vertex; ++i) {for (int j = 0; j < graph.vertex; ++j) {if (isVisted[i] && !isVisted[j] && graph.weight[i][j] < minWeight) {minWeight = graph.weight[i][j];index1 = i;index2 = j;}}}//找到的一条最小的边System.out.println("边<" + graph.data[index1] + "," + graph.data[index2] + "> weight:" + minWeight);isVisted[index2] = true;minWeight = Integer.MAX_VALUE;}}}class MGraph {int vertex; //表示图的结点个数char[] data; //保存结点的数据int[][] weight; //存放边,就是邻接矩阵public MGraph() {}public MGraph(int vertex, char[] data, int[][] weight) {this.vertex = vertex;this.data = data;this.weight = weight;}public void showGraph() {for (int[] ints : weight) {System.out.println(Arrays.toString(ints));}}//编写prim算法,得到最小生成树}