前言需要
明天咱们学习的是普里姆算法，咱们还是从一个场景里引入看看
有 7 个村庄(A, B, C, D, E, F, G)，当初须要修路把 7 个村庄连通
1. 各个村庄的间隔 用边线示意(权)，比方 A – B 间隔 5 公里
2. 问 如何修路保障各个村庄都能连通，并且总的建筑公路总里程最短?
咱们的思路就是尽可能的抉择少的路线，并且每条路线最小，保障总里程数起码
一、什么是普里姆算法
普利姆 (Prim) 算法求：最小生成树就是在 蕴含 n 个顶点的连通图 中，找出 只有 (n-1) 条边蕴含所有 n 个顶点的连通子图，也就是所谓的极小连通子图
二、通过示例意识普里姆算法
其实修路的问题实质就是最小生成树的问题
先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称 MST
那么什么是最小生成树呢？其实就是给定一个 带权的无向连通图 ，如何 选取一棵生成树，使树上所有边上权的总和为最小。这叫最小生成树
那么最小生成树有什么特点呢？
1. 若有 N 个顶点，肯定要至多有 N - 1 条边
2. 图要蕴含全副顶点
3.N- 1 条边要都在图中
那么求最小生成树的算法次要有普里姆算法和克鲁斯卡尔算法
普里姆算法思路剖析
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 条边
普里姆算法图解思路剖析
1. 如果从 A 顶点开始解决，将 A 放入汇合中，并可连贯到其余顶点有 C、G、B
2. 此时这三条边的最小权重值是 A -G 为 2，于是咱们 G 放入汇合中，《A，G》
3. 此时这五条边的最小权重值是 B -B 为 3，于是咱们 B 放入汇合中，《A，G，B》
4. 此时这四条边的最小权重值是 G -E 为 4，于是咱们 E 放入汇合中，《A，G，B，E》
此时这五条边的最小权重值是 E -F 为 5，以此类推退出到汇合中 ….
最初的汇合后果应该是 <A，G，B，E，F，D，C>
普里姆代码思路剖析
1. 咱们须要一个寄存顶点的 char 数组，以及顶点的边数
2. 咱们须要应用邻接矩阵来示意顶点之间的连贯状况与权重值
3. 咱们须要生成 minTree 树
4. 咱们须要创立图
普里姆算法代码实际
1. 应用邻接矩阵来示意图所之间连贯关系与权重值
// 应用邻接矩阵形容权重值示意 0 代表无
int[][] weight = new int[][]{{0,5,7,0,0,0,2},
{5,0,0,9,0,0,3},
{7,0,0,0,8,0,0},
{0,9,0,0,0,4,0},
{0,0,8,0,0,5,4},
{0,0,0,4,5,0,6},
{2,3,0,0,4,6,0}
}; 2. 须要一个寄存顶点的 char 数组，以及顶点的边数
//char[] 数组寄存顶点个数
char[] data = new char[]{'A','B','C','D','E','F','G'};
int verxs = data.length;3. 创立图对象
class MGraph{
int verxs;// 示意图的节点数
char[] data;// 寄存结点数据
int[][] weight;// 寄存边
public MGraph(int verxs) {
this.verxs = verxs;
data = new char[verxs];
weight = new int[verxs][verxs];
}
}4. 咱们须要将创立的这些值与数组、赋值给到图对象，并创立输入图的办法
class MinTree{
// 创立图的邻接矩阵
public void createGraph(MGraph graph,int verxs,char[] data,int[][] weight){for ( int i = 0 ; i<verxs;i++){
// 将 char 数组里的值赋值给图
graph.data[i] = data[i];
for (int j = 0; j<verxs;j++){
// 将 weight 里的值赋值给图
graph.weight[i][j] = weight[i][j];
}
}
}
// 打印图的信息
public void showGraph(MGraph graph){for ( int[] link : graph.weight){System.out.println(Arrays.toString(link));
}
}
}接下来咱们应用 demo 实现图的创立与输入
public static void main(String[] args) {//char[] 数组寄存顶点个数
char[] data = new char[]{'A','B','C','D','E','F','G'};
// 顶点之间的边
int verxs = data.length;
// 应用邻接矩阵形容权重值示意 0 代表无
int[][] weight = new int[][]{{0,5,7,0,0,0,2},
{5,0,0,9,0,0,3},
{7,0,0,0,8,0,0},
{0,9,0,0,0,4,0},
{0,0,8,0,0,5,4},
{0,0,0,4,5,0,6},
{2,3,0,0,4,6,0}
};
MGraph graph = new MGraph(verxs);
MinTree minTree = new MinTree();
minTree.createGraph(graph,verxs,data,weight);
minTree.showGraph(graph);
}
依据普里姆算法思路编写算法代码
1. 咱们的思路是先找到一个顶点开始，一直找相邻顶点，比如说 A 开始
找相邻顶点的条件是： A 已拜访，其余顶点为未拜访
2.判断 A - 其余顶点的 weight，是否是最小的
为了不便找到最小的，咱们这里应用一个很大的数，来代替刚刚的：0
public void prim(MGraph graph,int v){
// 应用数组标注节点是否被拜访过
int[] visited = new int[graph.verxs];
for (int i=0; i<visited.length; i++){visited[i] = 0;
}
// 将以后节点标注为已拜访
visited[v] = 1;
int h1 = -1;
int h2 = -1;
int minWeight = 10000;
for(int k = 1; k < graph.verxs; k++) {for(int i = 0; i < graph.verxs; i++) {for(int j = 0; j< graph.verxs;j++) {if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
System.out.println("边 <" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
visited[h2] = 1;
minWeight = 10000;
}
}行将上图所至的0 --> 10000
public static void main(String[] args) {//char[] 数组寄存顶点个数
char[] data = new char[]{'A','B','C','D','E','F','G'};
// 顶点之间的边
int verxs = data.length;
// 应用邻接矩阵形容权重值示意 0 代表无
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(verxs);
MinTree minTree = new MinTree();
minTree.createGraph(graph,verxs,data,weight);
minTree.showGraph(graph);
minTree.prim(graph,0);
}
运行后果如下：边 <A,G> 权值:2
边 <G,B> 权值:3
边 <G,E> 权值:4
边 <E,F> 权值:5
边 <F,D> 权值:4
边 <A,C> 权值:7参考资料
- 尚硅谷：数据结构与算法（韩顺平老师）：普里姆算法