最小生成树算法

Minimum cost spanning tree 最小生成树

最小生成树:

1. 定义：给定一个无向图,如何选取一颗生成树，使树上所有边上权的总和为最小

2. N个顶点，最少有N-1条边

3. 包含全部顶点

4. N-1条边都在图中

5. 普利姆和克鲁斯卡算法

prim 普利姆算法

是个最小生成树算法，计算包含n个顶点的连通图里的最小路径（找出n-1条边包含所有n个顶点的连通子图）

具体思路：

1. 从 <A> 顶点开始处理 -> <A,D>					<A,D>
	*A-D[5],A-B[7]
2. 从 <A,D> 顶点开始 -> <A,D,F>					 <D,F>
	A-B[7],D-B[9],D-E[15],*D-F[6]
3. 从 <A,D,F> 顶点开始 -> <A,D,F,B> 		 	 <A,B>
	*A-B[7],D-B[9],D-E[15],F-E[8],F-G[11],
4. 从 <A,D,F,B> 顶点开始 -> <A,D,F,B,E>  		 <B,E>
	D-B[9],D-E[15],F-E[8],F-G[11],B-C[8],*B-E[7]
5. 从 <A,D,F,B,E> 顶点开始 -> <A,D,F,B,E,C> 	 <E,C>
	D-B[9],D-E[15],F-E[8],F-G[11],B-C[8],E-G[9],*E-C[5]
6. 从 <A,D,F,B,E,C> 顶点开始 -> <A,D,F,B,E,C,G>  <E,G> (此处8为最小，但会构成回路，故排除选E-G)
	D-B[9],D-E[15],F-E[8],F-G[11],B-C[8],*E-G[9],E-F[8]

代码实现：

public class PrimAlgorithm {
	public static void main(String[] args) {
		char[] data = new char[] {'A','B','C','D','E','F','G'};
		int verxs = data.length;
		//邻接矩阵关系，10000表示两个点不连通
		int[][] weight = new int[][] {
			{10000,5,7,10000,10000,10000,2},
			{5,10000,10000,6,10000,10000,3},
			{7,10000,10000,10000,5,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,100000}
		};
		
		MGraph graph = new MGraph(verxs);
		
		MinTree minTree = new MinTree();
		minTree.createGraph(graph, verxs, data, weight);
		minTree.showGraph(graph);
		
		minTree.prim(graph, 0);
	}

}

//创建最小生成树
class MinTree {
	/**
	 * prim算法，得到最小生成树
	 * @param graph 图
	 * @param v 表示从图的第v个顶点开始
	 */
	public void prim(MGraph graph, int v) {
		
		//标记节点是否被访问过
		int visited[] = new int[graph.verxs];
		
		//把当前这个节点 标记为已访问
		visited[v] = 1;
		//记录两个顶点的下标
		int h1 = -1;
		int h2 = -1;
		//将 minWeight 初始化，后面遍历时会被替换
		int minWeight = 10000;
		//n个顶点（verxs），生成n-1个边
		for (int k = 1; k < graph.verxs; k++) {
			
			//确定每一次生成的子图，取出i到j节点的最近路径。i遍历访问过的节点
			for (int i = 0; i < graph.verxs; i++) {
				//j遍历访问过的节点
				for (int j = 0; j < graph.verxs; j++) {
					if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
						//替换minWeight
						minWeight = graph.weight[i][j];
						h1 = i;
						h2 = j;
					}
				}
			}
			//找到一条边
			System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">权值:" + minWeight);
			//将找到里i的最近边标记已访问
			visited[h2] = 1;
			
			minWeight = 10000;
		}
	}
	/**
	 * 创建图
	 * @param graph 图对象
	 * @param verxs 对应顶点个数
	 * @param data  各个顶点的值
	 * @param weight 图的邻接矩阵
	 */
	public void createGraph(MGraph graph,int verxs, char[] data,int[][] weight) {
		int  i,j;
		for(i = 0; i < verxs; i++) {
			graph.data[i] = data[i];
			for (j = 0; j < verxs; j++) {
				graph.weight[i][j] = weight[i][j];
			}
		}
	}
	xcc
	public void showGraph(MGraph graph) {
		for(int[] link : graph.weight) {
			System.out.println(Arrays.toString(link));
		}
	}
}

class MGraph {
	//节点个数
	int verxs;
	//节点数据
	char[] data;
	//存放边，邻接矩阵 
	int[][] weight;
	
	public MGraph(int verxs) {
		
		this.verxs = verxs;
		data = new char[verxs];
		weight = new int[verxs][verxs];
	}
}

​ kruskal 克鲁斯卡算法

求加权连通图的最小生成树算法。思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。做法：构成一颗含n个顶点的森林，然后权值从小到大从连通图中选择边加入到森林中，并使森林不构成回路，直到森林变成一棵树。

图片：

具体思路：

筛选出所有边权值（11条边）
A-D[5],A-B[7],D-B[9],D-E[15],D-F[6],B-E[7],B-C[8],C-E[5],E-G[9],E-F[8],F-G[11] 
按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
1. 选择权值最小的边 `1)` C-E[5],`2)` A-D[5]
2. 选择比次小的边 `3)` D-F[6]
3. `4)` A-B[7],`5)` B-E[7]
4. `6)` E-G[9]（B-D[9],B-C[8],E-F[8] 这两个会构成回路所以不选）

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： MISAKIGA
• 本文链接： https://misakiga.github.io/2020/05/13/algor/MST最小生成树算法/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！