谈谈Kruskal与Prim这两种最小生成树算法（Python实现）

Code

何为最小生成树




建立无导向图，使得这些点可以相互连通，并使得总权值最小。
如：


Kruskal

分析

定理：任何不包含最短边的数结构都还可以被做得更小，最小生成树中一定会包含最短边。
先对图中的边进行排序，然后着手选取。
对于每一条边，我们都会通过遍历来确定其对应的树结构上是否存在着从u到v的路径。
如果存在，我们就将其丢弃。
然后每次选取最小的边。直到无边可选。
根据权值排序

起点 终点 权值
1 2 1
1 3 2
4 6 3
5 6 4
2 3 6
4 5 7
3 4 9
2 4 11
3 5 13




对于2 3 6这条边，如果加上这条边就会形成回路。所以跳过




最后选用3 4 9这条边。我们已经选用了n-1条边，图已连通。



实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
G = {
    0:{},
    1: {1: 1, 2: 2},
    2: {1: 1, 3: 6, 4: 11},
    3: {1: 2, 2: 6, 4: 9, 5: 13},
    4: {2: 11, 3: 9, 5: 7, 6: 3},
    5: {3: 13, 4: 7, 6: 4},
    6: {4: 3, 5: 4},
}
'''
Kruskal算法
各种变量：
C：形如{u1:v1,u2:v2,....}的字典，主要用来寻找代表节点(祖先节点)。初始化，v1=u1,v2=u2....
如a-b-c-d {a:a,b:a,c:b,d:c}
G：图
E：列表，存放着形如(e,u,v)的字典，e：权值，u：源点，v：目标点
'''
def find(C, u):
    '''
寻找代表节点(祖先节点)
这里使用的是路径压缩的方法（path compression）
'''
    if C[u] != u:
        C[u] = find(C, C[u])
    return C[u]
def naive_union(C, u, v):
    '''
把较小的指向较大的
'''
    u, v = find(C, u), find(C, v)
    # u的祖先节点指向v的祖先节点
    C[u] = v
def kruskal(G):
    E = [(G[u][v], u, v) for u, _ in enumerate(G) for v in G[u]]
    T = set()
    C = {u: u for u, _ in enumerate(G)}
    for _, u, v in sorted(E):
        if find(C, u) != find(C, v): # 边的源点的祖先不等于边的目的祖先（因为相等的话说明该点已经添加过了，否则为默认值）
            T.add((u, v)) # 添加
            naive_union(C, u, v) # 合并，使目标节点变成生成树的一部分（修改其祖先）。
    return T,C
# ------测试结果---------
sum_count = 0
T = kruskal(G)
for k, v in T:
    sum_count += G[k][v]
print(sum_count)
print(sorted([i for i in T], key=lambda x: x[1]))
# 结果为19
# [(1, 2), (1, 3), (3, 4), (5, 6), (4, 6)]
# 以下为完成后的中间变量，便于理解
# C={0: 0, 1: 3, 2: 6, 3: 6, 4: 6, 5: 6, 6: 6}

Prim

分析

从某个起始节点开始对目标图结构进行遍历，并始终将最短的连接边加入到相应的树结构中。
说白了Prim算法就是另一种遍历型算法而已，遍历型算法之间的主要区别在于“待定”列表中的顺序。
在那些已被发现但没被访问的节点中，究竟哪一个是我们接下来要加入到遍历树种的节点。
在Prim算法中，我们将会采用堆结构来实现一个优先级队列。使得每次都pop权值最小的边
如果pop出的边的目的点已经在生成树里，便抛弃。否则便加入（注意：每次pop的都是权值最小的边）
我们可以任意选取一个顶点，然后看看它的边中哪一个最短的。

先从1开始，1-2=1；1-3=2。选取1-2




连通1,2之后，再从1,2开始找。1-3=2；2-3=6；2-4=11。选取1-3=2。如此类推




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def prim(G, s):
    P, Q = {}, [(0, None, s)]
    while Q:
        w, p, u = heappop(Q)
        if u in P: continue # 如果目标点在生成树中，跳过
        P[u] = p # 记录目标点不在生成树中
        for v, w in G[u].items():
            heappush(Q, (w, u, v)) # 将u点的出边入堆
    return P
# T = prim(G, 1)
# sum_count = 0
# for k, v in T.items():
# if v !=None:
# sum_count += G[k][v]
#
# print(sum_count)
# print(T)
# 结果为19
# {1: None, 2: 1, 3: 1, 4: 3, 5: 6, 6: 4}

Kruskal算法与prim算法

两个算法都使用了贪心的策略。

prim

  • 算法是某个起始节点开始对目标图结构进行遍历，将其所有的出边加入到最小堆里面
  • pop一条出边（每次pop的都是权值最小的边），然后判断这条边的目标点在生成树中
  • 如果是就丢弃
  • 不是就更新生成树

    Kruskal

  • 算法是将图中的边根据权值进行排序后从小到大遍历
  • 判断边的源点的祖先不等于边的目的祖先
  • 如果是就丢弃
  • 不是就加入
  • 然后更新生成树

    Kruskal算法与prim算法的结果相反的原因

    Kruskal算法：[(1, 2), (1, 3), (3, 4), (5, 6), (4, 6)]
    prim算法：{1: None, 2: 1, 3: 1, 4: 3, 5: 6, 6: 4}
    Kruskal算法记录的是从开始点到结束点的路径，1-2,1-3-4-6,5-6 关键代码：T.add((u,v))
    prim算法记录的是从结束点到开始点的路径，5-6-4-3-1,2-1 关键代码：P[u]=p

本文标题:谈谈Kruskal与Prim这两种最小生成树算法（Python实现）

文章作者:Vincent Zhong

发布时间:2016-10-10, 13:52:08

最后更新:2019-07-07, 13:13:10

原始链接:https://wax8280.github.io/2016/10/10/谈谈Kruskal与Prim这两种最小生成树算法（Python实现）/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 何为最小生成树
  2. 2. Kruskal
    1. 2.1. 分析
    2. 2.2. 实现代码
  3. 3. Prim
    1. 3.1. 分析
  4. 4. Kruskal算法与prim算法
    1. 4.1. prim
    2. 4.2. Kruskal
    3. 4.3. Kruskal算法与prim算法的结果相反的原因
|