热门标签
热门文章
- 1华为OD机试D卷 - 字符串变换最小字符串 - 免费看解析和代码_python 给定一个字符串s,最多只能进行一次变换
- 2政安晨的机器学习笔记——快速理解AI中的ML与DL概念_ai dl
- 3UMG 常用方法_loadclass
(nullptr, - 4机器学习python实践——关于数据集划分和数据标准化的相关问题的思考
- 5时序违例的解决思路_不同时钟 时序违例
- 6构建第一个ArkTS之页面和自定义组件生命周期
- 7windows server 2019-搭建文件共享服务器_windows sever2019服务器创建共享文件夹
- 8【干货】什么是CPU，GPU，ASIC和FPGA？_asic cpu
- 9深入分析 Android Service (六)(完)
- 10Android性能测试 之 APP&FPS的方法_安卓性能分析fpsgo
当前位置: article > 正文
程序员常用10种算法_十大算法及其应用场景
作者：你好赵伟 | 2024-06-29 22:53:54
赞
踩
十大算法及其应用场景
普里姆算法
应用场景—修路
- 有胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把 7 个村庄连通
- 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
- 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少
最小生成树
修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称 MST。给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
特点如下：N 个顶点，一定有 N-1 条边；包含全部顶点；N-1 条边都在图中
算法介绍
普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的连通子图，也就是所谓的极小连通子图
- 设 G=(V,E)是连通网，T=(U,D)是最小生成树，V,U 是顶点集合，E,D 是边的集合
- 若从顶点 u 开始构造最小生成树，则从集合 V 中取出顶点 u 放入集合 U
- 若集合 U 中顶点 ui 与集合 V-U 中的顶点 vj 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点 vj 加入集合 U 中，将边（ui,vj）加入集合 D 中，标记 visited[vj] = true
- 重复步骤2，直到 U 与 V 相等，即所有顶点都被标记为访问过，此时 D 中有 n-1 条边
图解说明：
package com.atguigu.prim; import java.util.Arrays; /** * @ClassName PrimDemo * @Author Jeri * @Date 2022-03-04 16:30 * @Description TODO */ //创建图类 class Graph{ int verCount;//图的顶点个数 char[] data;//存放顶点数据 int[][] weight;//存放邻接矩阵 boolean[] isVisited;//图的顶点是否被访问 public Graph(int vertexCount,char[] data,int[][] weight){ this.verCount = vertexCount; this.data = new char[verCount]; this.weight = new int[verCount][verCount]; this.isVisited = new boolean[verCount]; //使用 .clone() 方法进行深拷贝 this.data = data.clone(); this.weight = weight.clone(); } //显示图的邻接矩阵 public void show(){ for(int i = 0;i < verCount;i++){ for(int j = 0;j < verCount;j++){ System.out.printf("%-8d",weight[i][j]); } System.out.println(); } } } public class PrimDemo { public static void prim(Graph graph,int startVer){ //将开始顶点设置为已访问 graph.isVisited[startVer] = true; System.out.println("初始顶点为" + graph.data[startVer]); //使用 h1 和 h2 记录两个顶点的下标 int h1 = -1;//h1从已访问顶点集合中取 int h2 = -1;//h2从未访问顶点集合中取 //使用 minWeight 记录每一轮寻找到的最小路径 int minWeight = 10000; for(int k = 1; k < graph.verCount;k++){ //K表示未访问的节点数目 每进行一轮循环找到一个节点,并设置为已访问 for(int i = 0;i < graph.verCount;i++){ //i表示从已访问的节点出发 寻找未访问节点路径 if(graph.isVisited[i] == false) { continue;} for(int j = 0;j < graph.verCount;j++){ //j表示未访问的节点 if(graph.isVisited[j] == true) { continue;} if(minWeight > graph.weight[i][j]){ minWeight = graph.weight[i][j]; h1 = i; h2 = j; } } } //双 for 循环结束后 找到权值最小的边 System.out.println("当前添加 边:<" + graph.data[h1] + "," + graph.data[h2] + ">,权重为" + minWeight); //将找到的节点设置为已访问 graph.isVisited[h2] = true; //状态清零 minWeight = 10000; h1 = -1; h2 = -1; } } public static void main(String[] args) { //顶点集合 char[] data = new char[]{'A','B','C','D','E','F','G'}; //顶点个数 int vertexCount = 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}, }; //创建图对象 Graph graph = new Graph(vertexCount,data,weight); System.out.println("图的邻接矩阵如下：----"); graph.show(); System.out.println(); System.out.println("prim算法求得最小生成树结果如下：-----"); prim(graph,6); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
图的邻接矩阵如下：---- 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 prim算法求得最小生成树结果如下：----- 初始顶点为G 当前添加 边:<G,A>,权重为2 当前添加 边:<G,B>,权重为3 当前添加 边:<G,E>,权重为4 当前添加 边:<E,F>,权重为5 当前添加 边:<F,D>,权重为4 当前添加 边:<A,C>,权重为7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
克鲁斯卡尔算法
应用场景–公交站问题(最小生成树求解)
- 某城市新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通
- 各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里
- 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
算法介绍
- 将途中所有的边按照权值大小进行排序
- 依次将边添加到最小生成树，判断是否形成回路？
- 形成回路 ，则删除该边 转2
- 未形成回路 ，将将这条边 添加到结果集合 转2
并查集
并查集是一种树型结构，并查集可以高效的进行如下操作：
- 查询元素 p 和元素 q 是否属于同一组
- 合并元素 p 和 q 所在的组
并查集也是一种树形结构，要求比较简单：
- 每个元素都唯一的对应一个结点
- 每一组数据中的多个元素都在同一颗树中
- 一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系
- 元素在树中并没有子父级关系的硬性要求
并查集的实现：
- 初始情况下，每个元素都在一个独立的分组中，所以，初始情况下，并查集中的数据默认分为N个组；
- 初始化数组eleAndGroup；
- 把eleAndGroup数组的索引看做是每个结点存储的元素，把eleAndGroup数组每个索引处的值看做是该结点所在的分组，那么初始化情况下，i 索引处存储的值就是 i
package com.atguigu.kruskal; import java.util.Scanner; //并查集代码 class UF { //记录节点元素和该元素所在分组的表示 private int[] elementGroup; //记录并查集中数据的分组个数 private int count; //初始化并查集 public UF(int N) { //初始情况下 每个元素默认为一个独立的分组 this.count = N; //初始化数组 elementGroup = new int[N]; //elementGroup 数组 索引为其元素 索引值为其分组 for (int i = 0; i < N; i++) { elementGroup[i] = i; } } //获取当前并查集数据的分组总数 public int getCount() { return count; } //获取元素 p 所在分组标识符 public int find(int p) { return elementGroup[p]; } //判断并查集中元素p和元素q 是否在同一分组 public boolean connected(int p, int q) { return find(p) == find(q); } //把元素p所在分组和元素q所在分组进行合并 public void union(int p, int q) { if (connected(p, q)) { return; } int pGroup = find(p); int qGroup = find(q); for (int i = 0; i < elementGroup.length; i++) { if (elementGroup[i] == pGroup) { elementGroup[i] = qGroup; } } //分组数量 -1 count--; } } public class UTDemo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("请录入并查集中元素的个数:"); int N = sc.nextInt(); UF uf = new UF(N); while (true) { System.out.println("请录入您要合并的第一个点:"); int p = sc.nextInt(); System.out.println("请录入您要合并的第二个点:"); int q = sc.nextInt(); //判断p和q是否在同一个组 if (uf.connected(p, q)) { System.out.println("结点：" + p + "结点" + q + "已经在同一个组"); continue; } uf.union(p, q); System.out.println("总共还有" + uf.getCount() + "个分组"); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
请录入并查集中元素的个数: 5 请录入您要合并的第一个点: 0 请录入您要合并的第二个点: 2 总共还有4个分组 请录入您要合并的第一个点: 1 请录入您要合并的第二个点: 2 总共还有3个分组 请录入您要合并的第一个点: 1 请录入您要合并的第二个点: 0 结点：1结点0已经在同一个组
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
并查集代码的优化：
存在问题：上述代码在并查集合并时，需要遍历所有的元素，在实际中不可行
解决：eleAndGroup[i]的值不再是当前结点所在的分组标识，而是该结点的父结点
find(int p)查询方法实现：
- 判断当前元素p的父结点eleAndGroup[p]是不是自己，如果是自己则证明已经是根结点了
- 如果当前元素p的父结点不是自己，则让p=eleAndGroup[p]，继续找父结点的父结点,直到找到根结点为止
union(int p,int q)合并方法实现：
- 找到p元素所在树的根结点
- 找到q元素所在树的根结点
- 如果p和q已经在同一个树中，则无需合并
- 如果p和q不在同一个分组，则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可；
- 分组数量-1
package com.atguigu.kruskal; import java.util.Scanner; class UTTree{ //记录节点元素和该元素所在分组的表示 private int[] elementGroup; //记录并查集中数据的分组个数 private int count; //初始化并查集 public UTTree(int N) { //初始情况下 每个元素默认为一个独立的分组 this.count = N; //初始化数组 elementGroup = new int[N]; //elementGroup 数组 索引为其元素 索引值为其分组 for (int i = 0; i < N; i++) { elementGroup[i] = i; } } //获取当前并查集数据的分组总数 public int getCount() { return count; } //获取元素 p 所在分组标识符 public int find(int p) { while (true){ if(p == elementGroup[p]){ //当前节点的父节点就是自己 返回 return p; } //当前节点的父节点不是自己，让p = elementGroup[p] 继续查找父节点的父节点 //直到找到根节点为止 p = elementGroup[p]; } } //判断并查集中元素p和元素q 是否在同一分组 public boolean connected(int p, int q) { return find(p) == find(q); } //把元素p所在分组和元素q所在分组进行合并 public void union(int p, int q) { if(connected(p,q)){ return; } int pRoot = find(p); int qRoot = find(q); elementGroup[pRoot] = qRoot; count--; } } public class UTTreeDemo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("请录入并查集中元素的个数:"); int N = sc.nextInt(); UTTree utTree = new UTTree(N); while (true) { System.out.println("请录入您要合并的第一个点:"); int p = sc.nextInt(); System.out.println("请录入您要合并的第二个点:"); int q = sc.nextInt(); //判断p和q是否在同一个组 if (utTree.connected(p, q)) { System.out.println("结点：" + p + "结点" + q + "已经在同一个组"); continue; } utTree.union(p, q); System.out.println("总共还有" + utTree.getCount() + "个分组"); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
请录入并查集中元素的个数: 5 请录入您要合并的第一个点: 0 请录入您要合并的第二个点: 2 总共还有4个分组 请录入您要合并的第一个点: 1 请录入您要合并的第二个点: 2 总共还有3个分组 请录入您要合并的第一个点: 1 请录入您要合并的第二个点: 0 结点：1结点0：已经在同一个组
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
克鲁斯卡尔代码
package com.atguigu.kruskal; import java.util.ArrayList; import java.util.Collections; /** * @ClassName KruskalDemo * @Author Jeri * @Date 2022-03-04 17:20 * @Description 克鲁斯卡尔算法求最小生成树 */ //创建图类 class Graph{ int verCount;//图的顶点个数 char[] data;//存放顶点数据 int[][] weight;//存放邻接矩阵 boolean[] isVisited;//图的顶点是否被访问 public Graph(int vertexCount,char[] data,int[][] weight){ this.verCount = vertexCount; this.data = new char[verCount]; this.weight = new int[verCount][verCount]; this.isVisited = new boolean[verCount]; //使用 .clone() 方法进行深拷贝 this.data = data.clone(); this.weight = weight.clone(); } //显示图的邻接矩阵 public void show(){ for(int i = 0;i < verCount;i++){ for(int j = 0;j < verCount;j++){ if(weight[i][j] == Integer.MAX_VALUE){ System.out.printf("%-5s","INF"); }else{ System.out.printf("%-5d",weight[i][j]); } } System.out.println(); } } } //创建边类 class EdgeData implements Comparable<EdgeData>{ int start;//边的起点 int end;//边的终点 int weight;//边的权值 public EdgeData(int start, int end, int weight) { this.start = start; this.end = end; this.weight = weight; } @Override public String toString() { return "EdgeData{ <" + start + "," + end + "> " + "weight = " + weight + "}"; } //从小到大进行排序 @Override public int compareTo(EdgeData obj) { return this.weight - obj.weight; } } public class KruskalDemo { public static void kruskal(Graph graph){ //获取边的集合 ArrayList<EdgeData> edgeLists = new ArrayList<>(); for(int i = 0;i < graph.verCount;i++){ for(int j = i + 1;j < graph.verCount;j++){ if(graph.weight[i][j] != Integer.MAX_VALUE){ edgeLists.add(new EdgeData(i,j,graph.weight[i][j])); } } } System.out.println("边集 排序之前：" + edgeLists); //对边进行排序 Collections.sort(edgeLists); System.out.println("边集 排序之后：" + edgeLists); //创建并查集对象 UF uf = new UF(graph.verCount); for(int i = 0;i < edgeLists.size();i++){ if(uf.getCount() == 1){ //并查集中只有一个分组 说明最小生成树已经构建完成 break; } //得到边的起点和终点 EdgeData curretnEgde = edgeLists.get(i); int start = curretnEgde.start; int end = curretnEgde.end; if(uf.connected(start,end)){ // start end 在同一分组 不能添加 continue; }else{ uf.union(start,end); System.out.println("当前添加边 <" + graph.data[start] + "," + graph.data[end] + "> 权重为 " + graph.weight[start][end]); } } } //使用 INF 表示两个顶点不能连通 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} }; Graph graph = new Graph(vertexs.length,vertexs,matrix); System.out.println("图的邻接矩阵如下：-----------"); graph.show(); System.out.println("克鲁斯卡尔 排序结果:-------"); kruskal(graph); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
图的邻接矩阵如下：----------- 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 克鲁斯卡尔 排序结果:------- 边集 排序之前：[EdgeData{ <0,1> weight = 12}, EdgeData{ <0,5> weight = 16}, EdgeData{ <0,6> weight = 14}, EdgeData{ <1,2> weight = 10}, EdgeData{ <1,5> weight = 7}, EdgeData{ <2,3> weight = 3}, EdgeData{ <2,4> weight = 5}, EdgeData{ <2,5> weight = 6}, EdgeData{ <3,4> weight = 4}, EdgeData{ <4,5> weight = 2}, EdgeData{ <4,6> weight = 8}, EdgeData{ <5,6> weight = 9}] 边集 排序之后：[EdgeData{ <4,5> weight = 2}, EdgeData{ <2,3> weight = 3}, EdgeData{ <3,4> weight = 4}, EdgeData{ <2,4> weight = 5}, EdgeData{ <2,5> weight = 6}, EdgeData{ <1,5> weight = 7}, EdgeData{ <4,6> weight = 8}, EdgeData{ <5,6> weight = 9}, EdgeData{ <1,2> weight = 10}, EdgeData{ <0,1> weight = 12}, EdgeData{ <0,6> weight = 14}, EdgeData{ <0,5> weight = 16}] 当前添加边 <E,F> 权重为 2 当前添加边 <C,D> 权重为 3 当前添加边 <D,E> 权重为 4 当前添加边 <B,F> 权重为 7 当前添加边 <E,G> 权重为 8 当前添加边 <A,B> 权重为 12
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
迪杰斯特拉算法
应用场景-最短路径问题
- 战争时期，胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从 G 点出发，需要分别把邮件分别送到A,B, C , D, E, F 六个村庄
- 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
- 问：如何计算出 G 村庄到 其它各个村庄的最短距离?
- 如果从其它点出发到各个点的最短距离又是多少?
算法介绍
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止
- 设置出发顶点为 v，顶点集合 V{v1,v2,vi…}，v 到 V 中各顶点的距离构成距离集合 Dis，Dis{d1,d2,di…}，Dis集合记录着 v 到图中各顶点的距离(到自身可以看作 0，v 到 vi 距离对应为 di)
- 从 Dis 中选择值最小的 di 并移出 Dis 集合，同时移出 V 集合中对应的顶点 vi，此时的 v 到 vi 即为最短路径
- 更新 Dis 集合，更新规则为：比较 v 到 V 集合中顶点的距离值，与 v 通过 vi 到 V 集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为 vi，表明是通过 vi 到达的）
- 重复执行两步骤，直到最短路径顶点为目标顶点即可结束
代码实现
package com.atguigu.dijkstra; import java.util.Arrays; import java.util.Scanner; /** * @ClassName DijkstraDemo * @Author Jeri * @Date 2022-03-04 21:03 * @Description 迪杰斯特拉 算法 */ class Graph{ int verCount;//图的顶点个数 char[] data;//存放顶点数据 int[][] weight;//存放邻接矩阵 VisitedVertex vv; public Graph(int vertexCount,char[] data,int[][] weight,VisitedVertex vv){ //使用 .clone() 方法进行深拷贝 this.verCount = vertexCount; this.data = new char[verCount]; this.data = data.clone(); this.weight = new int[verCount][verCount]; this.weight = weight.clone(); this.vv = vv; } //显示图的邻接矩阵 public void show(){ for(int i = 0;i < verCount;i++){ for(int j = 0;j < verCount;j++){ if(weight[i][j] == 65535){ System.out.printf("%-5s","INF"); }else{ System.out.printf("%-5d",weight[i][j]); } } System.out.println(); } } // 通过 tempVertex 更新 初始节点到其他节点之间的距离 public void updateVertex(int tempVertex){ //tempVertex 表示中转节点 int directDis = 0; int indirectDis = 0; //遍历邻接节点所在的行 得到非直连距离和直连距离 // min((Lsk + Lkj) , Lsj) k = tempVertex // Lsk = vv.getDis(k) Lsj = vv.getDis(j) Lkj = weight[k][j] for(int j = 0;j < weight[tempVertex].length;j++){ // j表示当前顶点 indirectDis = vv.getDis(tempVertex) + weight[tempVertex][j]; directDis = vv.getDis(j); if( !vv.isVisited[j] && indirectDis < directDis){ //非直连 小于 直连 需要更新 //同时需要注意 当前的直连路径直接从 distance数组中返回 vv.updateDis(j,indirectDis); vv.updatePre(j,tempVertex); } } System.out.println("经过当前访问节点的距离数组："); System.out.println(Arrays.toString(vv.distance)); } public void dijkstra(int startVertex){ //更新初始节点 System.out.println("初始访问节点为" + data[startVertex]); updateVertex(startVertex); for(int i = 1;i < verCount;i++){ System.out.println(); int nextVertex = vv.updateVisted(); System.out.println("当前选择访问顶点为：" + data[nextVertex]); updateVertex(nextVertex); } } public void showPath(char end){ String path = ""; int startVertex = 6; int endVertex = 0; for(int i = 0;i < data.length;i++){ if(data[i] == end){ endVertex = i; break; } } int temp = endVertex; path = path + "--->" + data[endVertex]; while (vv.preVisited[temp] != startVertex){ temp = vv.preVisited[temp]; path = "--->" + data[temp] + path; } path = data[startVertex] + path; System.out.println("路径为" + path + ",距离为" + vv.getDis(endVertex)); } } class VisitedVertex{ //记录图中顶点是否被访问 public boolean[] isVisited ; //记录出发顶点到其他所有的顶点的距离 public int[] distance; //索引值作为前一个顶点的下标 寻找访问路径 public int[] preVisited; public VisitedVertex(int vertexCount,int startVertex){ isVisited = new boolean[vertexCount]; isVisited[startVertex] = true; distance = new int[vertexCount]; Arrays.fill(distance,65535);//初始化距离数组 distance[startVertex] = 0; preVisited = new int[vertexCount]; } //返回 初始顶点到当前顶点之间的距离 public int getDis(int tempVertex){ return distance[tempVertex]; } //更新 初始顶点到当前顶点之间的距离 public void updateDis(int CurrentVertex, int dis) { distance[CurrentVertex] = dis; } //更新 当前顶点之间为中继节点 public void updatePre(int CurrentVertex, int tempVertex) { preVisited[CurrentVertex] = tempVertex; } //选择新的访问顶点 public int updateVisted(){ int min = 65535; int nextVertex = 0; for(int i = 0;i < distance.length;i++){ if(!isVisited[i] && min > distance[i]){ min = distance[i]; nextVertex = i; } } //选择结束之后 //更新 访问顶点数组 isVisited[nextVertex] = true; return nextVertex; } } public class DijkstraDemo { public static final int N = 65535;// 表示不可以连接 public static void main(String[] args) { //顶点集合 char[] data = new char[]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //邻接矩阵 int[][] matrix = new int[][]{ {N,5,7,N,N,N,2}, {5,N,N,9,N,N,3}, {7,N,N,N,8,N,N}, {N,9,N,N,N,4,N}, {N,N,8,N,N,5,4}, {N,N,N,4,5,N,6}, {2,3,N,N,4,6,N} }; int startVertex = 6; VisitedVertex vv = new VisitedVertex(data.length,startVertex); Graph graph = new Graph(data.length,data,matrix,vv); System.out.println("图的邻接矩阵展示如下：------"); graph.show(); System.out.println("迪杰斯特拉算法运算结果如下：-----"); graph.dijkstra(startVertex); System.out.println(); Scanner scan = new Scanner(System.in); System.out.println("初始顶点:" + graph.data[startVertex]); System.out.println("请输入到达顶点(A-G):"); char end = scan.next().charAt(0); graph.showPath(end); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
图的邻接矩阵展示如下：------ INF 5 7 INF INF INF 2 5 INF INF 9 INF INF 3 7 INF INF INF 8 INF INF INF 9 INF INF INF 4 INF INF INF 8 INF INF 5 4 INF INF INF 4 5 INF 6 2 3 INF INF 4 6 INF 迪杰斯特拉算法运算结果如下：----- 初始访问节点为G 经过当前访问节点的距离数组： [2, 3, 65535, 65535, 4, 6, 0] 当前选择访问顶点为：A 经过当前访问节点的距离数组： [2, 3, 9, 65535, 4, 6, 0] 当前选择访问顶点为：B 经过当前访问节点的距离数组： [2, 3, 9, 12, 4, 6, 0] 当前选择访问顶点为：E 经过当前访问节点的距离数组： [2, 3, 9, 12, 4, 6, 0] 当前选择访问顶点为：F 经过当前访问节点的距离数组： [2, 3, 9, 10, 4, 6, 0] 当前选择访问顶点为：C 经过当前访问节点的距离数组： [2, 3, 9, 10, 4, 6, 0] 当前选择访问顶点为：D 经过当前访问节点的距离数组： [2, 3, 9, 10, 4, 6, 0] 初始顶点:G 请输入到达顶点(A-G): C 路径为G--->A--->C,距离为9
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
参考文献
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签
