最小生成树，最短路径算法

经典的贪心策略 Prim算法，Kruskal算法求最小生成树，dijkstra求最短路径

最小生成树算法 用到的并查集 在之前博客写，图都是下面的，最小生成树无向就行了

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
209
210
/**
 * 文件名：GraphTest2.java
 * 时间：2max14年11月17日下午6:2max:1max
 * 作者：修维康
 */
package chapter9;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
import chapter8.DisjSets;//并查集
/**
 * 类名：Edeg 说明：边
 */
class Edge {
	public int v1;
	public int v2;
	public int dist;
	public Edge(int v1, int v2, int dist) {
		this.v1 = v1;
		this.v2 = v2;
		this.dist = dist;// 权值
	}
}
class DistComparator implements Comparator<Edge> {
	@Override
	public int compare(Edge o1, Edge o2) {
		// TODO Auto-generated method stub
		if (o1.dist > o2.dist)
			return 1;
		else if (o1.dist < o2.dist)
			return -1;
		return 0;
	}
}
public class GraphTest2 {
	public static final int max = Integer.MAX_VALUE;
	/**
	 * 方法名：dijkstra 说明：迪杰斯克拉算法，V代表源 g存储图的信息，dist[i]代表到v到i的权,prev[i]代表 顶点i的前一个顶点
	 */
	public static void Dijkstra(int v, int n, int[][] g, int[] dist, int[] prev) {
		boolean[] s = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			dist[i] = g[v][i];
			s[i] = false;
			if (dist[i] == max)
				prev[i] = 0;
			else
				prev[i] = v;
		}
		s[v] = true;
		dist[v] = 0;
		// 从V-S中找到权值最小的边
		for (int i = 1; i < n; i++) {
			int temp = max;
			int u = v;
			for (int j = 1; j <= n; j++)
				if (!s[j] && temp > dist[j]) {
					temp = dist[j];
					u = j;
				}
			s[u] = true;
			// 更新
			for (int j = 1; j <= n; j++) {
				if (!s[j] && g[u][j] < max) {
					int newDist = dist[u] + g[u][j];
					if (newDist < dist[j]) {
						dist[j] = newDist;
						prev[j] = u;
					}
				}
			}
		}
	}
	/**
	 * 方法名：printPath 说明：打印最短路径
	 */
	public static void printPath(int[] prev, int v) {
		System.out.print(v + " ");
		while (prev[v] != 0) {
			System.out.print(prev[v] + " ");
			v = prev[v];
		}
	}
	/**
	 * 方法名：Prim 说明：最小生成树 Prim算法 lowcost[i]为顶点i到S集合中任意一点 最小的权值 closest[i]为
	 * S中与i顶点相连权值最小的顶点
	 */
	public static void Prim(int[][] g, int n) {
		boolean[] s = new boolean[n + 1];
		int[] lowcost = new int[n + 1];
		int[] closest = new int[n + 1];
		s[1] = true;
		lowcost[1] = 0;
		for (int i = 2; i <= n; i++) {
			lowcost[i] = g[1][i];
			closest[i] = 1;
			s[i] = false;
		}
		// 从V-S中找到与S中的顶点相连 且权值最小的点
		for (int i = 1; i < n; i++) {
			int min = max;
			int j = 1;
			for (int k = 2; k <= n; k++) {
				if (!s[k] && lowcost[k] < min) {
					min = lowcost[k];
					j = k;
				}
			}
			s[j] = true;
			System.out.println(j + "  " + closest[j]);
			// 重新更新 lowcost lowcost[i]为顶点i到S集合中任意一点 最小的权值
			for (int k = 2; k <= n; k++) {
				if (!s[k] && g[j][k] < lowcost[k]) {
					lowcost[k] = g[j][k];
					closest[k] = j;
				}
			}
		}
	}
	/**
	 * 方法名：Kruskal 说明：最小生成树 Kruskal算法
	 */
	public static void Kruskal(PriorityQueue<Edge> p, int n) {
		DisjSets ds = new DisjSets(n + 1);// 并查集
		Edge e;
		int edgesAccepted = 0;
		while (edgesAccepted < n - 1) {
			e = p.poll();
			int uset = ds.find(e.v1);
			int vset = ds.find(e.v2);
			if (uset != vset) {
				edgesAccepted++;
				System.out.println(e.v1 + " " + e.v2);
				ds.union1(uset, vset);
			}
		}
	}
	/**
	 * 方法名：main 说明：测试
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] g = new int[][] { { max, max, max, max, max, max, max, max },
				{ max, max, 2, max, 1, max, max, max },
				{ max, max, max, max, 3, 10, max, max },
				{ max, 4, max, max, max, max, 5, max },
				{ max, max, max, 2, max, 2, 18, 4 },
				{ max, max, max, max, max, max, max, 6 },
				{ max, max, max, max, max, max, max, max },
				{ max, max, max, max, max, max, 1, max } };
		// Graph graph = new Graph(g);
		int[] dist = new int[8];
		int[] prev = new int[8];
		Scanner in = new Scanner(System.in);
		System.out.println("请输入顶点号：");
		int v = in.nextInt();
		Dijkstra(v, 7, g, dist, prev);
		System.out.println("请输入目的顶点：");
		int n = in.nextInt();
		System.out.println("顶点" + v + "到顶点" + n + "的权值为" + dist[n]);
		printPath(prev, n);
		int[][] g2 = new int[][] { { max, max, max, max, max, max, max, max },
				{ max, max, 2, 4, 1, max, max, max },
				{ max, 2, max, max, 3, 10, max, max },
				{ max, 4, max, max, 2, max, 5, max },
				{ max, 1, 3, 2, max, 7, 8, 4 },
				{ max, max, 10, max, 7, max, max, 6 },
				{ max, max, max, 5, 8, max, max, 1 },
				{ max, max, max, max, 4, 6, 1, max } };
		Prim(g2, 7);
		PriorityQueue<Edge> p = new PriorityQueue<Edge>(12,
				new DistComparator());
		p.add(new Edge(1, 2, 2));
		p.add(new Edge(1, 4, 1));
		p.add(new Edge(2, 4, 3));
		p.add(new Edge(1, 3, 4));
		p.add(new Edge(3, 4, 2));
		p.add(new Edge(4, 5, 7));
		p.add(new Edge(2, 5, 10));
		p.add(new Edge(3, 6, 5));
		p.add(new Edge(4, 6, 8));
		p.add(new Edge(6, 7, 1));
		p.add(new Edge(4, 7, 4));
		p.add(new Edge(5, 7, 6));
		System.out.println("Kruskal算法：");
		Kruskal(p, 7);
	}
}