普里姆算法(修路问题)
一、是什么？
1. 应用场景：
有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通，各个村庄之间的距离如下。问如何修路，能使各个村庄连通且修路的总里程数最小？
修路问题
这就是经典的修路问题，就可以用普里姆算法来解决。
2.最小生成树：
要使总里程数最小，那么就要尽可能修少路，并且修的每条路距离应该小，这样加起来的总里程数才会少。这就是求最小生成树(MST)的过程。关于最小生成树，介绍如下：
- 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树 ；
- N个顶点，一定有N-1条边；
- 包含全部顶点；
- N-1条边都在图中；
什么意思呢？下面是一个图和它对应的生成树：
生成树
这是这个图对应的其中三种生成树，每条边有权值，权值加起来最小的那棵树，就叫做最小生成树。求最小生成树，可以用普里姆算法和克鲁斯卡尔算法。
二、普里姆算法步骤：
修路问题
还是以这个图为例，普里姆算法过程如下：
- 创建一个集合，保存选择的顶点。首先选取顶点A，表示从A开始处理，将A加入到集合中。与A直接连通的有C、B、G，其中AG的权值最小，所以选择的是G，G加入到集合中。
- 现在集合中有A和G，和A直接诶连通且还没有访问过的顶点有C、B，和G直接连通且还没有访问过的顶点有E、B、F。其中权值最小的是GB，所以选择B，B加入到集合。
- 现在集合中有A、G、B。和A直接连通且没访问过的有C，和G直接连通且没访问过的是E、F，和B直接连通且没访问过的是D。其中权值最小的GE，所以选择E，E加入到集合。
……
- 按照上面的方法，直到所有村庄都加到了集合中。最后选择的是AGBEFDC。
三、代码实现：
要用代码实现上述过程，首先我们要用邻接矩阵将这个图构建出来。首先创建一个类，表示图：
/**
* 图
* @author zhu
*
*/
class Graph{
List<String> vertexs; // 存放顶点
int[][] edges; // 邻接矩阵，存放边
public Graph(List<String> vertexs, int[][] edges) {
this.vertexs = vertexs;
this.edges = edges;
}
}然后，创建一个最小生成树类：
class MinTree{
/**
* 创建图
* @param vertex 顶点集合
* @param edges 邻接矩阵
*/
public Graph createGraph(List<String> vertex, int[][] edges) {
return new Graph(vertex, edges);
}
/**
* 打印图的二维数组
* @param graph
*/
public void printGraph(Graph graph) {
int[][] edges = graph.edges;
for (int i=0; i<edges.length; i++) {
System.out.println(Arrays.toString(edges[i]));
}
}
}现在，就要在最小生成树类中用普里姆算法创建最小生成树，中MinTree类中加一个方法，如下：
/**
* 普里姆算法创建最小生成树
* @param graph 图
* @param currentVertex 开始处理的顶点
*/
public Map<String, Integer> prim(Graph graph, String currentVertex) {
Map<String, Integer> resultMap = new HashMap<>(); // 保存结果的集合，key是两个顶点，value是这两个顶点边的长度
List<String> vertexs = graph.vertexs; // 图的顶点
int vertexCount = vertexs.size(); // 顶点的个数
int currentVertexIndex = vertexs.indexOf(currentVertex); // 当前处理顶点的索引
boolean[] isVisited = new boolean[vertexCount]; // 顶点是否被访问过
isVisited[currentVertexIndex] = true; // 标记当前处理的顶点为已访问
int num = 10000; // 初始化一个较大的数，用来比较权值的
int index1 = -1; // 记录找到的两个顶点的索引
int index2 = -1; // 记录找到的两个顶点的索引
// n个顶点要生成n-1条边，所以循环n-1次
for (int times=0; times<vertexCount-1; times++) {
for (int i=0; i<vertexCount; i++) { // i表示访问过的顶点
for (int j=0; j<vertexCount; j++) { // j表示未访问过的顶点
if (isVisited[i] && !isVisited[j] && graph.edges[i][j] < num) {
num = graph.edges[i][j];
index1 = i;
index2 = j;
}
}
}
resultMap.put("<" + vertexs.get(index1) + "," + vertexs.get(index2) + ">", num);
isVisited[index2] = true;
// 重置num
num = 10000;
}
return resultMap;
}关于这个方法也很好理解，也有详细的注释。下面就可以写个测试方法，将案例中的图构建出来，求出修路的方案：
public static void main(String[] args) {
List<String> vertexs = new ArrayList<>();
vertexs.add("A");
vertexs.add("B");
vertexs.add("C");
vertexs.add("D");
vertexs.add("E");
vertexs.add("F");
vertexs.add("G");
int[][] edges = new int[][] {
// 100表示没有连通
//A B C D E F G
{100, 5, 7, 100, 100, 100, 2}, // A
{ 5, 100, 100, 9, 100, 100, 3}, // B
{ 7, 100, 100, 100, 8, 100, 100},// C
{100, 9, 100, 100, 100, 4, 100},// D
{100, 100, 8, 100, 100, 5, 4}, // E
{100, 100, 100, 4, 5, 100, 6}, // F
{ 2, 3, 100, 100, 4, 6, 100} // G
};
MinTree minTree = new MinTree();
Graph graph = minTree.createGraph(vertexs, edges);
Map<String, Integer> resultMap = minTree.prim(graph, "A");
for (String key : resultMap.keySet()) {
System.out.println(key + ": " + resultMap.get(key));
}
}最后的结果是：
修路方案
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读