朝小闇的博客

海上月是天上月,眼前人是心上人

Prime和Kruskal

Prime算法和Kruskal算法都是无向图中最短路径算法,给出例证场景如下:

1

注:代码部分基本上复用博客https://blog.csdn.net/weixin_43312097/article/details/108238521#comments_14014195

Prime算法

简要介绍

  • 最小生成树算法,从顶点的角度出发,适合解决边稠密的连通网;
  • 时间复杂度为n2,以下代码为n3
  • 从已访问顶点开始,每次查找已访问边集合到未访问边集合中的最短未完全访问路径,直到找到n-1条边结束;

主要思想

  1. 将所有顶点划分成已访问和未访问两个集合;
  2. 从已访问集合依次取出一个顶点作为出度;
  3. 从未访问集合依次取出一个顶点作为入度;
  4. 取以该出入度为顶点的边的最小值并记录,将该最小值的入度顶点移动到已访问集合;
  5. 假设共有n个顶点,循环n-1次即找到所有边;

基于邻接矩阵实现

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
import java.util.Arrays;

public class Prime {
// 常量MAX定义为无穷大,即没有边
final static int MAX = Integer.MAX_VALUE;

public static void main(String[] args) {
// 总顶点个数
int vertex = 7;
// 每个顶点对应的名字
char[] name = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
// 从该顶点开始
int start = 0;
// (无向图)邻接矩阵必须转置相等的
int[][] weight = new int[][]{
{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}};
Graph graph = new Graph(vertex, name, weight);
int[] res = prime(graph, start);
for (int i = 0; i < vertex; i++) {
System.out.println(name[i]+"-"+name[res[i]]);
}
}

/**
* @param graph
* @param start 从哪个顶点开始
*/
private static int[] prime(Graph graph, int start) {
// 存储路径中依次与顶点相连接最短边顶点的索引
int[] res = new int[graph.getVertexs()];
// 将数组全部初始化填充为-1
Arrays.fill(res, -1);
// 标识位,表示该索引对应顶点是否已被连接访问
boolean[] visited = new boolean[graph.getVertexs()];
Arrays.fill(visited, false);
visited[start] = true;
// 一条边上连接的两个顶点
int h1 = -1;
int h2 = -1;
// 最小权值,初始化为无穷大
int minWeight = MAX;
// 对于n个节点的数,我们最多只需要找到n-1个边就能把所有的节点相连,所以下边的循环从1开始
for (int k = 1; k < graph.getVertexs(); k++) {
// 第一层表示找访问过的节点
for (int i = 0; i < graph.getVertexs(); i++) {
// 第二层找没有访问过的节点 ,同时找最小权值的边
for (int j = 0; j < graph.getVertexs(); j++) {
if (visited[i] && !visited[j] && minWeight > graph.getWeight()[i][j]) {
// 不断更新
minWeight = graph.getWeight()[i][j];
h1 = i;
h2 = j;
}
}
}
// 重置
minWeight = MAX;
// 这次循环找到的边
System.out.println("边为:<" + graph.getName()[h1] + "," + graph.getName()[h2] + "> 权重为:" + graph.getWeight()[h1][h2]);
// 访问过的边记录下来
visited[h2] = true;
if (res[h1] == -1) {
res[h1] = h2;
}
if (res[h2] == -1) {
res[h2] = h1;
}
}
// 返回索引数组
return res;
}
}

class Graph {
private int vertexs;
private char[] name;
private int[][] weight;

/**
* @param vertexs 顶点的个数
* @param name 顶点的名称
* @param weight 邻接矩阵
*/
public Graph(int vertexs, char[] name, int[][] weight) {
if (vertexs != name.length || weight.length != vertexs || weight[0].length != vertexs) {
throw new RuntimeException("初始化异常!");
}
this.vertexs = vertexs;
this.name = name;
this.weight = weight;
}
public int getVertexs() {
return vertexs;
}

public char[] getName() {
return name;
}

public int[][] getWeight() {
return weight;
}
}

>>
边为:<A,G> 权重为:2
边为:<G,B> 权重为:3
边为:<G,E> 权重为:4
边为:<E,F> 权重为:5
边为:<F,D> 权重为:4
边为:<A,C> 权重为:7
A-G
B-G
C-A
D-F
E-G
F-E
G-A

思考

  1. 类私有属性以及外部方法接口调用的实现;
  2. 使用注解注释方法参数等;
  3. Prime算法中对于其初始顶点的选择,多使用一个参数flag作为循环次数即可;
  4. 数组填充方法Arrays.fill(visited, false);的使用;
  5. 对于异常情形的处理;

Kruskal算法

简要介绍

  • 从边的角度求网的最小生成树;
  • 适用于边稀疏的网的最小生成树;
  • 从网中最短边开始查找,排除两个顶点都已经访问过的边,直到找到n-1条边结束;

主要思想

  1. 将所有边进行排序;
  2. 对每一个顶点设置一个连接索引,初始化为自身,当找到合适的边时则记录值为边的另一个顶点索引;
  3. 重复找到n-1条边;

基于邻接矩阵实现

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
package demo01.Prime_Kruskal;

import java.util.Arrays;
import java.util.HashMap;

public class Kruskal {
final static int MAX = Integer.MAX_VALUE;

public static void main(String[] args) {
int vertex = 7;
char[] name = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
// (无向图)邻接矩阵必须转置相等的
int[][] weight = new int[][]{
{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}};
GraphK graph = new GraphK(vertex, name, weight);
kruskal(graph);
}


public static int[] kruskal(GraphK graph) {
// 创建并初始化所有边
Edg[] edgs = new Edg[graph.getEdg_num()];
int index = 0;
for (int i = 0; i < graph.getVertexs(); i++) {
for (int j = i + 1; j < graph.getVertexs(); j++) {
if (graph.getWeight()[i][j] != Integer.MAX_VALUE) {
edgs[index++] = new Edg(graph.getName()[i], graph.getName()[j], graph.getWeight()[i][j]);
}
}
}
// 对边进行排序,这里还有点问题
Arrays.sort(edgs);
// 开始选择边,初始化为自身索引,一旦发现适合的边则修改其值为边顶点索引
int[] res = new int[graph.getVertexs()];
// 为了通过节点的名字获取索引就定义了一个map
HashMap<Character, Integer> getIndex = new HashMap<>();
index = 0;
for (char c : graph.getName()) {
res[index] = index;
// 增加键值对映射
getIndex.put(c, index++);
}
int sum = 0;
// 因为只需要找到n-1条边 ,所以定义一个计数器提前返回
int count = 0;
for (int i = 0; i < edgs.length && count < graph.getVertexs(); i++) {
Edg edg = edgs[i];
// 取出字符对应索引值
int start = getIndex.get(edg.start);
int end = getIndex.get(edg.end);
//
int start_root = find(res, start); // 寻找节点的根节点
int end_root = find(res, end); // 寻找节点的根节点
// 如果不相等 那么说明不构成回路,可以添加到候选集合中
if (start_root != end_root) {
// 找到边,修改索引
res[end_root] = start_root;
sum += edg.dis;
System.out.println(graph.getName()[start] + ">" + graph.getName()[end] + " 距离为:" + edg.dis);
count++;
}
}
System.out.println("总路径为:" + sum);
// 返回索引数组
return res;
}


/**
* 寻找根节点 类似并查集的思路
*
* @param res
* @param i
* @return
*/
private static int find(int[] res, int i) {
int i_root = i;
// while实现下标递归直到res[i]=i结束循环,找到连通边的终点
while (res[i_root] != i_root) {
i_root = res[i_root];
}
return i_root;
}


}

/**
* 需要实现lang包下的接口 这样可以直接进行排序
*/

class Edg implements Comparable<Edg> {
public char start;
public char end;
public int dis;

public Edg(char start, char end, int dis) {
this.start = start;
this.end = end;
this.dis = dis;
}

/**
* 重写方法,这一段没理解,应该是对sort()比较其中dis属性的含义
*
* @param o
* @return
*/
@Override
public int compareTo(Edg o) {
return dis - o.dis;
}
}

class GraphK {
private int vertexs;
private char[] name;
private int[][] weight;
// 图中所有边的总数
private int edg_num;

/**
* @param vertexs 顶点的个数
* @param name 顶点的名称
* @param weight 邻接矩阵
*/
public GraphK(int vertexs, char[] name, int[][] weight) {
if (vertexs != name.length || weight.length != vertexs || weight[0].length != vertexs) {
throw new RuntimeException("初始化异常!");
}
this.vertexs = vertexs;
this.name = name;
this.weight = weight;

//计算边的条数
for (int i = 0; i < vertexs; i++) {
for (int j = i + 1; j < vertexs; j++) {
if (weight[i][j] < Integer.MAX_VALUE) {
edg_num++;
}
}
}
}

public int getVertexs() {
return vertexs;
}

public char[] getName() {
return name;
}

public int[][] getWeight() {
return weight;
}

public int getEdg_num() {
return edg_num;
}
}

>>
A>G 距离为:2
B>G 距离为:3
D>F 距离为:4
E>G 距离为:4
E>F 距离为:5
A>C 距离为:7
总路径为:25

思考

  1. Comparable接口的实现,方便对类中具体属性进行Array.sort()排序;
  2. 根索引res[]以及while的使用,找到连通网的终点;
  3. HashMap键值对映射与匹配取值;
-------- 本文结束 感谢阅读 --------