42-MST & Prim 算法

应用场景：修路问题

最小生成树

定义

• 加权图：一种为每条边关联一个权值的图模型

• 图的生成树：是该连通图的一个极小连通子图，含有图的全部顶点，但只有构成一棵树的(n-1)条边
  

• 一幅加权图的最小生成树(MST)：在生成树的基础上，要求树的(n-1)条边的权值之和是最小的
  

一些约定

• 只考虑连通图
  • 根据树的基本性质，我们要找的就是一个由V-1条边组成的集合，他们既连通了图中的所有顶点而权值之和又最小
  • 如果一幅图是非连通的，我们只能使用这个算法来计算它的所有连通分量的最小生成树，合并在一起称其为"最小生成森林"
• 边的权重可能是0或者负数
• 所有边的权重都各不相同
  • 如果可以相同，MST就不一定唯一了

计算MST的两种算法

• Prim 算法
• Kruskal 算法

Prim 算法

• 从任意一个顶点开始，每次选择一个与 当前顶点集 最近的一个顶点，并将两顶点之间的边加入到顶点集中。然后继续找 离更新后的这个顶点集 最近的顶点 ....，就这么找下去，找够 n-1 条边
• {顶点集} 是逐渐增大的
• 找 {当前最近顶点} 时使用到了贪婪算法

思路分析

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 条边

代码实现

public class PrimDemo {
	public static void main(String[] args) {
		char[] datas = new char[] {'A','B','C','D','E','F','G'};
		int vertexs = datas.length;
		// 邻接矩阵 (∵ 是加权边 ∴ 表示两个顶点不连通得用个大数而非0)
		int[][] weightEdges = 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}
		};
		
		MST mst = new MST();
		mst.createGraph(vertexs, datas, weightEdges);
		mst.showGraph();
		mst.prim(4);
	}
}

class MST {
	private Graph graph;
	
	public void createGraph(int vertexs, char[] datas, int[][] weightEdges) {
		graph = new Graph(vertexs);
		int i, j;
		for(i = 0; i < vertexs; i++) {
			graph.datas[i] = datas[i];
			for(j = 0; j < vertexs; j++)
				graph.weightEdges[i][j] = weightEdges[i][j];
		}
	}
	
	/**
	 * 普利姆算法
	 * @param v 从图的 v顶点 开始生成MST E.G. 'A' → 0, 'B' → 1 ...
	 */
	public void prim(int v) {
		// 标记 顶点是否已被访问
		int[] visited = new int[graph.vertexs];
		// 把当前结点标记为 1
		visited[v] = 1;
		// 记录选定的2个顶点的索引
		int h1 = -1;
		int h2 = -1;
		
		int minWeight = 10000;
		// n个顶点, 找出 n-1 条边
		for(int k = 1; k < graph.vertexs; k++) {
			
			// 双重for: 确定 [新一次生成的子图(图越来越大)] 中, 哪两个顶点的权值最小
			// ~ 顶点i 表示被访问的结点(也同是子图中的顶点)
			for(int i = 0; i < graph.vertexs; i++) {
				// ~ 顶点j 表示还没有被访问的结点
				for(int j = 0; j < graph.vertexs; j++) {
					// 子图越来越大, 需要if的次数也越来越多
					if(visited[i] == 1 && visited[j] == 0 
							&& graph.weightEdges[i][j] < minWeight) {
						minWeight = graph.weightEdges[i][j];
						h1 = i;
						h2 = j;
					}
				}
			}
			System.out.printf("<%c, %c>	weight = %d
"
					, graph.datas[h1], graph.datas[h2], minWeight);
			visited[h2] = 1;
			minWeight = 10000;
		}
	}
	
	public void showGraph() {
		graph.showGraph();
	}
}


class Graph {
	int vertexs; // 图中顶点个数
	char[] datas; // 顶点的值
	int[][] weightEdges; // 加权边
	
	public Graph(int vertexs) {
		this.vertexs = vertexs;
		datas = new char[vertexs];
		weightEdges = new int[vertexs][vertexs];
	}
	
	public void showGraph() {
		for(int[] link : weightEdges)
			System.out.println(Arrays.toString(link));
	}
}