在学习最小生成树之前，我们先来看看一个很实用的算法：并查集
并查集
并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题。此数据结构有两种操作：
- 1、Find：确定元素属于哪一个子集。这个确定方法就是不断向上查找找到它的根节点，它可以被用来确定两个元素是否属于同一子集。
- 2、Union：将两个子集合并成同一个集合。
为了更加精确的定义这些方法，需要定义如何表示集合。
一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x) 返回 x 所属集合的代表，而 Union 使用两个集合的代表作为参数。
如果是以树的概念来看的话
在并查集树中，每个集合的代表即是集合的根节点。
查找根据其父节点的引用向根行进直到到底树根。联合将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。
如果不做任何的处理，创建的树可能会严重不平衡，因此一般会有如下两个优化点
按秩合并
即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。在这个算法中，术语秩即表示深度，因为同时应用了路径压缩时（见下文）秩将不会与高度相同。单元素的树的秩定义为0，当两棵秩同为r的树联合时，它们的秩r+1
路径压缩
即是一种在执行查找时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上；他们都有同样的表示方法。为了达到这样的效果，Find递归地经过树，改变每一个节点的引用到根节点。得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。
以冗余连接为例
class UnionQuerySet(object):
def __init__(self, n):
self.parents = [val for val in range(n)]
self.ranks = [0] * n
def find(self, val):
# 路径压缩
if self.parents[val] != val:
self.parents[val] = self.find(self.parents[val])
return self.parents[val]
def is_connected(self, val1, val2):
return self.find(val1) == self.find(val2)
def union(self, val1, val2):
p1 = self.find(val1)
p2 = self.find(val2)
if p1 == p2:
return
# 按秩合并
if self.ranks[p1] > self.ranks[p2]:
self.parents[p2] = p1
elif self.ranks[p1] < self.ranks[p2]:
self.parents[p1] = p2
else:
self.parents[p1] = p2
self.ranks[p2] += 1
class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
union_query_set = UnionQuerySet(10001)
for edge in edges:
if union_query_set.is_connected(edge[0], edge[1]):
return edge
else:
union_query_set.union(edge[0], edge[1])Kruskal算法
Kruskal基于并查集算法来找到最小生成树。
算法步骤
- 1、初始化并查集
- 2、根据权重对边进行排序。
- 3、遍历排序后的边，判断该边对应的两个顶点是否联通，然后将其联通，并加入生成树
时间复杂度
- 1、初始化生成树的边集A为空集：
O(1) - 2、对集合中的每一个顶点，都将它的集合初始化为自身：
O(V) - 3、将边按权值进行排序：
O(ElogE) - 4、对排序好后的边从小到大进行判断，如果这条边所连的2个顶点不在同一个集合中，则将这条边加入到生成树的边集A中，并将此边所连的两个顶点u和v的集合做一个Union操作，如此循环加到生成树中的边集数量为n-1时停止：
O(V+E)α(V)
具体证明过程在《算法导论》的并查集章节里
由于各个子块不是嵌套的而是顺序的，所以时间复杂度取最高的那个即为O(ElogE)
模板代码
#coding:utf-8
X = dict()
R = dict()
# 初始化并查集
def make_set(point):
X[point] = point
R[point] = 0
# 找到节点的根
def find(point):
if X[point] != point:
X[point] = find(X[point])
return X[point]
# 连接两个节点
def merge(point1,point2):
r1 = find(point1)
r2 = find(point2)
if r1 != r2:
if R[r1] > R[r2]:
X[r2] = r1
else:
X[r1] = r2
if R[r1] == R[r2]:
R[r2] += 1
#KRUSKAL算法实现
def kruskal(graph):
# 遍历顶点，初始化并查集
for vertex in graph['vertexs']:
make_set(vertex)
k_tree = []
edges = graph['edges']
# 按照权重从小到大排序
edges.sort()
# 遍历每一条边
for weight, vertex1, vertex2 in edges:
# 判断两个顶点是否联通：即是否在属于一棵树
if find(vertex1) != find(vertex2):
# 如果未联通，则将其联通
merge(vertex1, vertex2)
# 加入生成树
k_tree.add(edge)
return k_tree
# 如下调用
graph = {
'vertices': ['A', 'B', 'C', 'D', 'E', 'F'],
'edges': [(1, 'A', 'B'),
(5, 'A', 'C'),
(3, 'A', 'D'),
(4, 'B', 'C'),
(2, 'B', 'D'),
(1, 'C', 'D')]
}
kruskal(graph)Prim算法
Prim基于贪心算法找到最小生成树。
算法步骤
- 1、边权信息初始化：根据语言特征，可以采用不同的数据结构，比如python，可以采用字典，key为每一个顶点，value为与该顶点直连的点、边、权值组成的列表。
- 2、选择源点：任意选择一个顶点作为源点，将该点对应的边权信息表加入小顶堆中，保证每次取出的都是权值最小的边。
- 3、遍历小顶堆：每次都堆中取出权值最小的边，将该边加入结果生成树中。然后将该对端点对应的边权信息表加入小顶堆中。
注：需要判断点是否已选择，因此需要有标记列表
时间复杂度
如果是基于邻接矩阵，则O(V2)
如果是基于邻接表，O(ElogV)
模板代码
#coding:utf-8
from collections import defaultdict
from heapq import *
def prim(origin_vertex, edges):
adjacent_vertex = defaultdict(list)
# 将edges列表中各项归类成以某点为dictionary的key，其value则是其相邻的点及其权重
# 形如：{'A': [(7, 'A', 'B'), (5, 'A', 'D')],
# 'C': [(8, 'C', 'B'), (5, 'C', 'E')]}
for vertex1, vertex2, weight in edges:
adjacent_vertex[vertex1].append((weight, vertex1, vertex2))
adjacent_vertex[vertex2].append((weight, vertex2, vertex1))
p_tree = []
# 标记是否已选择：这里首先选择源点
chosed = set(origin_vertex)
# 得到与源点直连的相邻点边
adjacent_vertexs_edges = adjacent_vertex[origin_vertex]
# 将源点所有的直连边加入小顶堆中
heapify(adjacent_vertexs_edges)
# 循环遍历小顶堆
while adjacent_vertexs_edges:
# 从堆中取出边权值最小的点信息。
weight, vertex1, vertex2 = heappop(adjacent_vertexs_edges)
# 如果边权值最小的对端点还没有加入生成树中
if vertex2 not in chosed:
# 将该点标记已选择
chosed.add(vertex2)
# 将该最小边加入生成树中
p_tree.append((vertex1,vertex2,weight))
# 遍历与该点直连的相邻点边
for next_vertex in adjacent_vertex[vertex2]:
# 如果该点的对端点还没有被选择，则将其对应的边加入堆中
if next_vertex[2] not in chosed:
heappush(adjacent_vertexs_edges,next_vertex)
return p_tree
# 如下调用
vertexs = list("ABCDEFG")
edges = [ ("A", "B", 7), ("A", "D", 5),
("B", "C", 8), ("B", "D", 9),
("B", "E", 7), ("C", "E", 5),
("D", "E", 15), ("D", "F", 6),
("E", "F", 8), ("E", "G", 9),
("F", "G", 11)]
prim(vertexs[0], edges)
评论 (10)
