最小生成树及Go实现算法

一个生成树指的是图的一个子集,包含有所有的定点以及可能的最小数量的边, 生成树本身可以有多个比如下面的例子。并且生成树本身不能是分离且具有回环的。具有的属性如下:

  • 一个连通的无向图至少包含一个生成树

  • 每一个生成树具有相同数目的边和顶点

  • 不包含回环

  • 移除任何一个边,都会导致整个图的分离

  • 增加任何一个边,都会导致创建一个回环

Spanning Trees

生成树主要用于查找一个拓扑图中最短的路径连接,比如给出任何两个点,查找出最佳的连接。比如:

  • 网络路由协议
  • 集群连接分析
  • 网络规划等

比如如果看做不同城市构建的网络,在城市间铺设电话线路,如何才能达到最节约成本的构建方式。在一个具有权重的图中,最小生成树指的是一个生成树具有最小的权重值,这个权重在现实中可以表示为距离,延迟,流量负载或者任何自定义的值。当 V 个定点的时候,最小生成树总是包含有 V-1 个边,这在后面的算法中被用于作为循环的终止条件

比较著名的最小生成树算法分别是:

  • Kruskal 算法
  • Prim 算法

两种算法均属于贪婪算法,

Kruskal 算法流程

Kruskal 算法的主要步骤如下:

  • 按照每个节点权重进行排序
  • 将排序结果送入处理器处理(Union-Find 算法查询是否出现回环)
  • 当未出现回环时候,写入结果集合,当结果集数量=V-1 时退出
  • 当出现回环时候,简单的删除该组数据即可
  • 返回最终的数据集合

堆排序

进行排序操作这里使用堆排序算法,该算法输入是所有的边信息以及权重信息,依次读取堆中最小数据即完成了整个的排序和取值操作。我们可以自定义堆结构,或者使用Go标准库中的Container/Heap来实现。这里采用第二种,

这里假设有一个节点3->4权重为2, 我们使用一个[3]int{3,4,2}结构存储节点信息, 因此所有的边信息可以统一的放入一个容器[][3]int中。

import "container/heap"


type PriorityQueue [][3]int

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i][2] < pq[j][2]
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, (x).([3]int))
}
func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	item := (*pq)[n-1]
	*pq = (*pq)[0 : n-1]
	return item
}

图结构的数据存储模型如下面所示, 其中的uf仅作为UnionFind算法使用,初始化函数中将其设置为节点当前的索引位置数值

type Graph struct {
	v     int
	e     int
	edges [][3]int
	uf    []int
}

func NewGraph(v int, e int, data [][3]int) *Graph {
	graph := Graph{
		v:     v,
		e:     e,
		edges: data,
		uf:    make([]int, v),
	}
	for i := 0; i < graph.v; i++ {
		graph.uf[i] = i
	}
	return &graph
}

UnionFind算法

这里的 Union-Find 算法实现回环的检查,该算法原理比较简单

  • 假设有N个元素
  • 初始化一个N元素大小的Parent数组(存储其父元素),并依次设置为[0,N-1]
  • Union将元素0, 5进行连接,比如下面的Union(0,5) 设置Parent[5] = 0
  • Union将元素5,6进行连接,设置Parent[6] = 0
  • 最终数组中数据一致的为一个分组
  • 假如这时候我们有一个新的连接0,6,通过检查发现0, 6 具有相同的Root,因此这个连接必定会引入一个Cycle

“union find”的图片搜索结果

该部分的代码如下:


func (graph *Graph) find(p int) int {
	root := p
	for root != graph.uf[root] {
		root = graph.uf[root]
	}

	for p != root {
		next := graph.uf[p]
		graph.uf[p] = root
		p = next
	}
	return root
}

func (graph *Graph) connected(p int, q int) bool {
	return graph.find(p) == graph.find(q)
}

func (graph *Graph) unify(p, q int) {
	rootP := graph.find(p)
	rootQ := graph.find(q)
	if rootP == rootQ {
		return
	}
	graph.uf[rootP] = rootQ
}


实例

图结构如下所示:

img

首先进行排序操作, 列出权重值以及该组数据的起始点和终止点:

Weight   Src    Dest
1         7      6
2         8      2
2         6      5
4         0      1
4         2      5
6         8      6
7         2      3
7         7      8
8         0      7
8         1      2
9         3      4
10        5      4
11        1      7
14        3      5

对于上面的拓扑图列表数据,依次检查是否出现回环,比如循环到8->6节点时候,我们可以通过直观看到形成了一个[2,8,6,5,2]的闭环,因此该组数据将被忽略。最终形成的结构如下面所示:

img

发表评论

邮箱地址不会被公开。 必填项已用*标注