prim算法和Kruskal算法
2021/12/26 22:10:58
本文主要是介绍prim算法和Kruskal算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 一、prim算法
- 1.基本介绍
- 2.应用场景——修路问题
- 3.代码实现
- 二、Kruskal算法
- 1.基本介绍
- 2.应用场景
- 3.代码实现
一、prim算法
1.基本介绍
普利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找出只有(n-1)条边包含所有n个顶点的连通子图,也就是所谓的极小连通子图
普利姆的算法如下:
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条边
2.应用场景——修路问题
3.代码实现
package com.tx.prim; import java.util.Arrays; public class Prim { public static void main(String[] args) { char[] data = new char[]{'A','B','C','D','E','F','G'}; int verxs = 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(verxs); MinTree minTree = new MinTree(); minTree.createGraph(graph, verxs, data, weight); minTree.showGraph(graph); minTree.primMethod(graph, 1); } } //创建最小生成树 class MinTree { public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) { int i, j; for(i = 0; i < verxs; i++) {//顶点 graph.data[i] = data[i]; for(j = 0; j < verxs; j++) { graph.weight[i][j] = weight[i][j]; } } } public void showGraph(MGraph graph) { for(int[] link: graph.weight) { System.out.println(Arrays.toString(link)); } } public void primMethod(MGraph graph, int v) { int visited[] = new int[graph.verxs]; visited[v] = 1; //h1 和 h2 记录下标 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 minWeight = 10000; } } } class MGraph { int verxs; //表示图的节点个数 char[] data;//存放结点数据 int[][] weight; //存放边,就是我们的邻接矩阵 public MGraph(int verxs) { this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; } }
二、Kruskal算法
1.基本介绍
克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。
基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路。
具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止。
2.应用场景
3.代码实现
代码如下(示例):
ipackage com.tx.kruskal; import java.util.Arrays; public class Kruskal { private int edgeNum; //边的个数 private char[] vertexs; //顶点数组 private int[][] matrix; //邻接矩阵 //表示两个顶点不能连通 private static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //邻接矩阵 int matrix[][] = { { 0, 12, INF, INF, INF, 16, 14}, { 12, 0, 10, INF, INF, 7, INF}, { INF, 10, 0, 3, 5, 6, INF}, { INF, INF, 3, 0, 4, INF, INF}, { INF, INF, 5, 4, 0, 2, 8}, { 16, 7, 6, INF, 2, 0, 9}, { 14, INF, INF, INF, 8, 9, 0}}; Kruskal kruskalCase = new Kruskal(vertexs, matrix); kruskalCase.print(); kruskalCase.kruskalmethod(); } public Kruskal(char[] vertexs, int[][] matrix) { int vlen = vertexs.length; this.vertexs = new char[vlen]; for(int i = 0; i < vertexs.length; i++) { this.vertexs[i] = vertexs[i]; } this.matrix = new int[vlen][vlen]; for(int i = 0; i < vlen; i++) { for(int j= 0; j < vlen; j++) { this.matrix[i][j] = matrix[i][j]; } } for(int i =0; i < vlen; i++) { for(int j = i+1; j < vlen; j++) { if(this.matrix[i][j] != INF) { edgeNum++; } } } } public void kruskalmethod() { int index = 0; int[] ends = new int[edgeNum]; EData[] rets = new EData[edgeNum]; EData[] edges = getEdges(); System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12 sortEdges(edges); //遍历edges 数组 for(int i=0; i < edgeNum; i++) { //获取到第i条边的第一个顶点 int p1 = getPosition(edges[i].start); //获取到第i条边的第2个顶点 int p2 = getPosition(edges[i].end); int m = getEnd(ends, p1); //获取p2到终点 int n = getEnd(ends, p2); //是否构成回路 if(m != n) { ends[m] = n; rets[index++] = edges[i]; } } System.out.println("最小生成树为"); for(int i = 0; i < index; i++) { System.out.println(rets[i]); } } public void print() { System.out.println("邻接矩阵为: \n"); for(int i = 0; i < vertexs.length; i++) { for(int j=0; j < vertexs.length; j++) { System.out.printf("%12d", matrix[i][j]); } System.out.println(); } } private void sortEdges(EData[] edges) { for(int i = 0; i < edges.length - 1; i++) { for(int j = 0; j < edges.length - 1 - i; j++) { if(edges[j].weight > edges[j+1].weight) {//交换 EData tmp = edges[j]; edges[j] = edges[j+1]; edges[j+1] = tmp; } } } } private int getPosition(char ch) { for(int i = 0; i < vertexs.length; i++) { if(vertexs[i] == ch) { return i; } } return -1; } private EData[] getEdges() { int index = 0; EData[] edges = new EData[edgeNum]; for(int i = 0; i < vertexs.length; i++) { for(int j=i+1; j <vertexs.length; j++) { if(matrix[i][j] != INF) { edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges; } private int getEnd(int[] ends, int i) { [0,0,0,0,5,0,0,0,0,0,0,0] while(ends[i] != 0) { i = ends[i]; } return i; } } //创建一个类EData来表示一条边 class EData { char start; //边的一个点 char end; //边的另外一个点 int weight; //边的权值 public EData(char start, char end, int weight) { this.start = start; this.end = end; this.weight = weight; } @Override public String toString() { return "EData [<" + start + ", " + end + ">= " + weight + "]"; } }
这篇关于prim算法和Kruskal算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现