一.问题引入

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算法,得到最小生成树}