最小生产树Prim和Kruskal

前言

春节将至,提前祝大家新春快乐,万事如意。今天介绍无向图最小生产树。

无向图最小生成树问题描述

一个无向图G的最小生成树就是由该图的那些链接G的所有顶点的边构成的树,其总价值最低。 最小生成树存在当且仅当图是连通的。为了简便考虑, 下面的算法都是假设图是连通的。 无向图最小生成树有两个典型的算法Prim和Kruskal,下面分别介绍。

Prim算法

算法核心思想

以贪婪策略,一步一步将关联顶点增加到树上。

算法介绍

算法的每一阶段都是通过:

  1. 选择一条边(u,v)使得(u,v)的值是所有u在树上但v不在树上的边的值中的最小者。并把相应的顶点v添加到这颗树上。
  2. 继续上述步骤,直到所有顶点都在树上。

图解示例

核心代码

public void prim(Vertex start){
	//初始声明所有顶点均不在树上
	for(Vertex v:graph){
		v.isInTree=false;
		v.dist=Integer.MAX_VALUE;
	}
	start.dist = 0;// 声明起点的距离为0
	//以顶点的最短距离构建堆
	PriorityQueue<Vertex> priorityQueue = new PriorityQueue<Vertex>();
	priorityQueue.add(start);
	while(!priorityQueue.isEmpty()){
		Vertex v=priorityQueue.poll();
		if(v!=null){
	          if(!v.isInTree){//取出的顶点不在树上
			//1. 声明顶点在树上
			v.isInTree=true;
			if(v.adj!=null&&!v.adj.isEmpty()){
				for(AdjVertex adjw:v.adj){
				//更新临接表中 最短距离有变化的顶点,并将该顶点加入到优先队列
					if(adjw.cvw<adjw.w.dist){
					    adjw.w.setDist(adjw.cvw);
					    adjw.w.setPath(v);
					    priorityQueue.add(adjw.w);
						}
					}
				}
			}
		}
	}
}

Kruskal算法

算法核心思想

以贪婪策略,连续按照最小的权选择备选边,并且当所选的边不会产生圈时选定该边。

算法介绍

分析

Kruskal类似处理一个森林。初始时,有存在|V|颗单节点树,每添加一条边即将两棵树合并,当算法终止时就只有一颗树。

数据结构选择

  1. 经过上述分析,Kruskal所需要的数据结构需要很好的支持find(即找到节点所属的当前树)和union操作(即合并两颗树)。目前良好的支持find/union操作的数据结构就是不相交集合
  2. 每次选择最小权的边。以边的权构建堆,每次执行deletemin操作。

算法核心

在算法的任意时刻,两个顶点属于同一个集合当且仅当它们在当前的生成森林中连通。

图解示例

核心代码

public List<Edge> kruskal() {
	List<Edge> result = new ArrayList<Edge>();
	int vertexSize = graph.values().size();
	int acceptedEdge = 0;
	//以点的数量构建不相交集合
	DisjSets disjSets = new DisjSets(vertexSize);
	//以边的权构建堆
	PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>(getEdges());
	while (acceptedEdge < vertexSize - 1&&!priorityQueue.isEmpty()) {
		Edge e = priorityQueue.poll();
		int disv = disjSets.find(e.vnum);
		int disw = disjSets.find(e.wnum);
		if (disv != disw) {
			//两个顶点不在一颗树上,合并两个顶点
				acceptedEdge++;
				disjSets.union(disv, disw);
				result.add(e);
			}
	}
	return result;
}

完整代码地址

github Prim

Kruskal

码云

Prim

Kruskal

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

数据结构 数组和广义表以及树的基本概念

2-1 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为 (2分) 1...

2578
来自专栏数据结构与算法

二分图相关定理

定义:若选择一个点说明选择与它相连的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。

1193
来自专栏算法channel

基本算法|图解各种树(三)

01 AVL树 二叉树,可以退化到单链,也可以满二叉树,用到二叉树时编码的方便,常常虚拟出一种真二叉树,还说到了一种特列(二叉树)来描述多叉树的方法。 基本算...

3715
来自专栏程序生活

Leetcode-Easy 70. Climbing Stairs

21. Merge Two Sorted Lists 描述: 有n阶楼梯,每步只能走1个或2个台阶,请问到达第n阶楼梯一共有多少走法? ? ...

3296
来自专栏郭耀华‘s Blog

知乎问题代码

1152
来自专栏数据结构与算法

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

27710
来自专栏编程理解

数据结构(七):图

图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关...

1233
来自专栏WD学习记录

Python数据结构与算法笔记(5)

邻接矩阵优点是简单,对于小图,很容易看到哪些节点连接到其他节点。但是大多数单元格是空的,即稀疏。

1313
来自专栏趣学算法

数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n...

1722
来自专栏云霄雨霁

加权有向图----单点最短路径问题(Dijkstra算法)

2510

扫码关注云+社区

领取腾讯云代金券