我是靠谱客的博主 苹果方盒,最近开发中收集的这篇文章主要介绍用Java【普利姆算法】解决修路问题,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

一、介绍

  • 普利姆(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条边

二、最小生成树

  • 修路问题本质就是就是最小生成树问题, 先介绍一下最小生成树(Minimum Cost Spanning Tree),简称MST。
  1. 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
  2. N个顶点,一定有N-1条边
  3. 包含全部顶点
  4. N-1条边都在图中
  5. 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法。
    例图:
    在这里插入图片描述

三、应用场景-修路问题

  • 有胜利乡有7个村庄(A, B, C, D, E, F, G) ,现在需要修路把7个村庄连通
  • 各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里
  • 问:如何修路保证各个村庄都能连通,并且总的修建公路总里程最短?
    在这里插入图片描述
  • 思路:尽可能的选择少的路线,并且每条路线最小,保证总里程数最少。

四、代码实现

复制代码
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
/** * 普利姆算法 */ public class PrimAlgorithm { public static void main(String[] args) { final int max = Integer.MAX_VALUE; char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int peaks = data.length; //邻接矩阵的关系使用二维数组表示 int[][] weight = { {max, 5, 7, max, max, max, 2}, {5, max, max, 9, max, max, 3}, {7, max, max, max, 8, max, max}, {max, 9, max, max, max, 4, max}, {max, max, 8, max, max, 5, 4}, {max, max, max, 4, 5, max, 6}, {2, 3, max, max, 4, 6, max} }; //创建一个MinTree对象 MinTree minTree = new MinTree(peaks, data, weight); minTree.showResult(); } } /** * 创建最小生成树 / 图 */ class MinTree { //用于保存基本图 MinGraph graph; //保存结果集 resultPeak[] result; int resultIndex; public MinTree(int peaks, char data[], int[][] weight) { //创建MinGraph对象 graph = new MinGraph(peaks); //创建结果集 result = new resultPeak[peaks]; //创建图 createGraph(peaks, data, weight); //运行普利姆算法 prim(graph, 1); } /** * 创建图 * * @param peaks 顶点个数 * @param data 顶点的值 * @param weight 邻接矩阵 */ public void createGraph(int peaks, char data[], int[][] weight) { for (int i = 0; i < peaks; i++) { graph.data[i] = data[i]; for (int j = 0; j < peaks; j++) { graph.weight[i][j] = weight[i][j]; } } } /** * 显示邻接矩阵 * * @param graph 邻接矩阵 */ public void showGraph(MinGraph graph) { System.out.println("----------邻接矩阵----------"); for (int[] link : graph.weight) { for (int i = 0; i < link.length; i++) { System.out.printf("%12d", link[i]); } System.out.println(); } System.out.println("----------邻接矩阵----------"); } /** * 得到最小生成树 * * @param graph * @param index */ public void prim(MinGraph graph, int index) { // 标记顶点是否被访问过,默认值为0,代表没访问过,访问过设为1 int visited[] = new int[graph.peakSize]; // 把当前结点标记为已访问 visited[index] = 1; //记录两个顶点的下标 int peakIndex1 = -1; int peakIndex2 = -1; //将minWeight 初始化为Integer.MAX_VALUE; int minWeight = Integer.MAX_VALUE; // for (int k = 1; k < graph.peakSize; k++) { for (int i = 0; i < graph.peakSize; i++) { for (int j = 0; j < graph.peakSize; j++) { //判断已访问过的结点 和 未访问过的结点间的最小权值的边 if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) { //替换minWeight minWeight = graph.weight[i][j]; peakIndex1 = i; peakIndex2 = j; } } } //找到权值最小的一条边,将其保存 result[resultIndex++] = new resultPeak(graph.data[peakIndex1],graph.data[peakIndex2],minWeight); // System.out.println("边<" + graph.data[peakIndex1] + "," + graph.data[peakIndex2] + "> weight:" + minWeight); //将当前这个结点标记为已访问 visited[peakIndex2] = 1; //将minWeight恢复默认 minWeight = Integer.MAX_VALUE; } } /** * 输出结果集 */ public void showResult() { System.out.println("----------结果集----------"); for (int i = 0; i < result.length; i++) { if(result[i] != null){ System.out.println(result[i]); } } System.out.println("----------结果集----------"); } } /** * 图对象 */ class MinGraph { //图的节点个数 int peakSize; //节点数据 char[] data; //存放边,邻接矩阵 int[][] weight; public MinGraph(int peakSize) { this.peakSize = peakSize; data = new char[peakSize]; weight = new int[peakSize][peakSize]; } } class resultPeak { char begin; char end; int weight; public resultPeak(char begin, char end, int weight) { this.begin = begin; this.end = end; this.weight = weight; } @Override public String toString() { return "resultPeak{" + begin + " --> " + end + " weight=" + weight + '}'; } }

最后

以上就是苹果方盒为你收集整理的用Java【普利姆算法】解决修路问题的全部内容,希望文章能够帮你解决用Java【普利姆算法】解决修路问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(55)

评论列表共有 0 条评论

立即
投稿
返回
顶部