大胡子

数据结构与算法系列之无向加权图的最小生成树算法-Kruskal算法

发表于

解决问题

上一篇已经讲到一种算法解决最小生成树问题，那么这篇同样是解决这个问题，用到的算法是Kruskal算法
那么除了讲解这种算法的实现代码，将会对这两种算法进行时间复杂度比较，在什么情况下选择不同的算法

问题

假设点A,B,C,D,E,F，两点之间有连线的，以及它们的距离分别是：(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)
那么首先通过图的邻接矩阵表示形式，如下：
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) ]

##算法实现

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#encoding=utf-8
#coding:utf-8
#以全局变量X定义节点集合，即类似{'A':'A','B':'B','C':'C','D':'D'},如果A、B两点联通，则会更改为{'A':'B','B':'B",...},即任何两点联通之后，两点的值value将相同。
X = dict()
#各点的初始等级均为0,如果被做为连接的的末端，则增加1
R = dict()
#设置X R的初始值
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):
    print point1 + "的的指向为" + X[point1]
    print point2 + "的的指向为" + X[point2]
    r1 = find(point1)
    r2 = find(point2)
    print r1,r2
    if r1 != r2:
        if R[r1] > R[r2]:
            X[r2] = r1
            print "大于"
            print r2 + "指向了" + X[r2]
            print r1+"连通值为"+str(R[r1])
            print r2+"连通值为"+str(R[r2])
        else:
            X[r1] = r2
            print r1 + "指向了" + X[r1]
            if R[r1] == R[r2]: R[r2] += 1
            print r1 + "连通值为" + str(R[r1])
            print r2 + "连通值为" + str(R[r2])
#KRUSKAL算法实现
def kruskal(graph):
    for vertice in graph['vertices']:
        make_set(vertice)
    minu_tree = set()
    edges = list(graph['edges'])
    edges.sort()#按照边长从小到达排序
    print edges
    for edge in edges:
        weight, vertice1, vertice2 = edge
        print "*+*+*+*+**+*+*+*+*+*+*+*+*+*+*+*+*"
        if find(vertice1) != find(vertice2):
            merge(vertice1, vertice2)
            minu_tree.add(edge)
        else:
            print vertice1+"---"+X[vertice1]+"and"+vertice2+"---"+X[vertice2]
            print "相等之后直接忽略"
    return minu_tree
if __name__=="__main__":
    graph = {
        'vertices': ['A', 'B', 'C', 'D', 'E', 'F','G'],
        'edges': set([
            (7, 'A', 'B'),
            (5, 'A', 'D'),
            (8, 'B', 'C'),
            (9, 'B', 'D'),
            (7, 'B', 'E'),
            (5, 'C', 'E'),
            (15,'D', 'E'),
            (6, 'D', 'F'),
            (8, 'E', 'F'),
            (9, 'E', 'G'),
            (11,'F', 'G')
            ])
        }
    result = kruskal(graph)
    print result