普里姆算法(Prim)
1.应用场景-修路问题
看一个应用场景和问题：
(1)有胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通
(2)各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
(3)问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
2.最小生成树(MST)
(1)修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。
(2)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
(3)N个顶点，一定有N-1条边
(4)包含全部顶点
(5)N-1条边都在图中
(6)举例说明(如图:)
(7)求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
3.普里姆算法介绍
普利姆(Prim)算法求最小生成树，也就是在包含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
- 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边
4.普利姆算法的图解分析
1.从< A>顶点开始处理，将< A>顶点和他们相邻的还没有访问的顶点进行处理,找到路径最小的边 <A,G>，权值：2，此时，被访问过的结点为：<A,G>
A-C [7] A-G[2] A-B[5] => A-G[2] 最小
2. <A,G> 开始 , 将<A,G>顶点和他们相邻的还没有访问的顶点进行处理,找到路径最小的边 <G,B> ，权值：3，此时，被访问过的结点为：<A,G,B>
A-C[7] A-B[5] G-B[3] G-E[4] G-F[6] =>G-B[3] 最小
3. <A,G,B> 开始，将<A,G,B>顶点和他们相邻的还没有访问的顶点进行处理,找到路径最小的边 <G,E> ，权值：4，此时，被访问过的结点为：<A,G,B,E>
A-C[7] G-E[4] G-F[6] B-D[9] =>G-E[4] 最小
4.<A,G,B,E> 开始，将<A,G,B,E>顶点和他们相邻的还没有访问的顶点进行处理,找到路径最小的边 <E,F> ，权值：5，此时，被访问过的结点为：<A,G,B,E,F>
A-C[7] E-F[5] G-F[6] B-D[9] =>E-F[5] 最小
5.<A,G,B,E,F> 开始，将<A,G,B,E,F>顶点和他们相邻的还没有访问的顶点进行处理,找到路径最小的边 <F,D> ，权值：4，此时，被访问过的结点为：<A,G,B,E,F,D>
A-C[7] E-C[8] F-D[4] B-D[9] =>F-D[4] 最小
6. <A,G,B,E,F,D> 开始，将<A,G,B,E,F,D>顶点和他们相邻的还没有访问的顶点进行处理,找到路径最小的边 <A,C> ，权值：7，此时，被访问过的结点为：<A,G,B,E,F,D,C>
A-C[7] E-C[8] B-D[9] =>A-C[7] 最小
此时，所有的结点都被访问过了，并且连接的路径最小
- 完整代码如下：
import java.util.Arrays;
public class PrimAlgorithm {
public static void main(String[] args) {
char[] data = new char[]{'A','B','C','D','E','F','G'};
int vertexs = data.length;
//邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
int [][]weight=new int[][]{
{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 graph = new MGraph(vertexs);
graph.setData(data);
graph.setWeight(weight);
graph.showGraph();
MinTree tree = new MinTree();
tree.prim(graph, 0);
}
}
class MinTree{
/**
* 普利姆算法，得到最小生成树
* @param graph 需要得到最小生成树的图
* @param v 从图的那个节点开始生成最小生成树
*/
public void prim(MGraph graph, int v){
System.out.println("连接所有结点并且路径最小的边为：");
//标记顶点是否访问过，默认为0 表示未访问过
int visited[] = new int[graph.vertexs];
//因为是从第v个结点开始生成最小生成树的，所以刚开始需要把第v个结点置为已访问
visited[v] = 1;
//h1 h2 记录两个结点的下标
int h1 = -1;
int h2 = -1;
//初始化最小距离为10000(初始化最小举例为一个比较大的数即可，然后在查找最短路径时会被替换)
int minWeight = 100000;
for (int k = 1; k < graph.vertexs; k++) { //共graph.vertexs个结点，至少需要 graph.vertexs - 1条边来连接
for (int i = 0; i < graph.vertexs; i++) { //i表示已访问过的结点
if(visited[i] != 1){ //如果i不是已访问过的结点，则寻找下一个节点
continue;
}
for (int j = 0; j < graph.vertexs; j++) { //j表示未访问过的结点
if(visited[j] != 0){
continue;
}
//如果当前minWeight 大于 当前两个结点(这两个结点一个为已访问，一个为未访问)的最小路径，则替换当前的最小路径为当前两个结点的路径
if(minWeight > graph.weight[i][j]){
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
//此时找的一条最小路径
System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">,权值 = " + graph.weight[h1][h2]);
//将h2指向的结点置为已访问
visited[h2] = 1;
//重置最小路径
minWeight = 100000;
}
}
}
//图
class MGraph{
int vertexs; //图顶点的个数
char[] data; //顶点数据
int[][] weight; //图的边，用邻接矩阵表示
public MGraph(int vertexs) {
this.vertexs = vertexs;
data = new char[vertexs];
weight = new int[vertexs][vertexs];
}
public char[] getData() {
return data;
}
public void setData(char[] data) {
this.data = data;
}
public int[][] getWeight() {
return weight;
}
public void setWeight(int[][] weight) {
this.weight = weight;
}
//显示图的邻接矩阵
public void showGraph(){
System.out.println("图的邻接矩阵为：");
for (int[] link : weight) {
System.out.println(Arrays.toString(link));
}
}
}
- 结果：
