大胡子

发表于

解决问题

本算法主要解决的是无向加权图中找出权值最小的最小生成树，关于什么是最小生成树等基本概念本文不介绍

问题

假设点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
#encoding=utf-8
from collections import defaultdict
from heapq import *
def prim(vertexs,edges):
    #创建一个一键多值的字典
    heaplist_adjacent = defaultdict(list)
    #将键为每个顶点的每条边放在列表值上
    for v1,v2,len in edges:
        heaplist_adjacent[v1].append((len,v1,v2))
        heaplist_adjacent[v2].append((len,v2,v1))
    #构造返回的最小生成树列表
    mst = []
    #将已经走过的顶点加入到一个集合中
    have_walk = set(vertexs[0])
    #将字典中第一个顶点的对应的列表放进要排序的list中
    edgescompare_list = heaplist_adjacent[vertexs[0]]
    #进行堆排序
    heapify(edgescompare_list)
    #只要排序的list中由元素
    while edgescompare_list:
        #弹出边的权值最小的那个
        len,v1,v2 = heappop(edgescompare_list)
        print (len,v1,v2)
        #如果不再已走过的顶点中
        if v2 not in have_walk:
            #将新的顶点加入已走过的集合中
            have_walk.add(v2)
            #将这条信息加入到最小生成树中
            mst.append((v1,v2,len))
            #接下来操作是将这个顶点的所有边加入到列表中进行排序，前提是不包括加入mst中的边
            for next_vertex in heaplist_adjacent[v2]:
                if next_vertex[2] not in have_walk:
                    heappush(edgescompare_list,next_vertex)
    return mst
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)]
print "edges:",edges
print "prim:", prim(vertexs, edges)
大胡子

发表于

解决问题

上一篇已经讲到一种算法解决最小生成树问题，那么这篇同样是解决这个问题，用到的算法是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

大胡子

发表于

引入始末

python3中出现的yield from对coroutine编程提供了极大的好处，那么在之前出现的yield关键字，充当一个什么样的作用呢。
原本的yield语句只能将cpu控制权还给调用者，(这里引申出一个重要的一点就是多线程编程与协程编程同样都是切换，一个是在cpu角度，一个是在用户程序角度)，当你想要在一个generater或者couroutine里带有yield语句的逻辑重构到另外一个generater中的时候，会非常麻烦。因为外层的生成器要为里层的生成器做消息传递，所以就需要吧这一层消息封装起来，这样有了yield from的出现

例子说明

当我们简单的使用yield去进行嵌套generater编程的时候，那么我们的代码会非常的繁琐，那么我们一起看看

1
2
3
4
5
6
7
8
9
10
11
def inner():
    coef = 1
    total = 0
    while True:
        try:
            input_val = yield total
            total = total + coef * input_val
        except SwitchSign:
            coef = -(coef)
        except BreakOut:
            return total

那么外层的将会是这样，当然消费者生产者模型跟这个非常像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def outer1():
    print("Before inner(), I do this.")
    i_gen = inner()
    input_val = None
    ret_val = i_gen.send(input_val)
    while True:
        try:
            input_val = yield ret_val
            ret_val = i_gen.send(input_val)
        except StopIteration:
            break
        except Exception as err:
            try:
                ret_val = i_gen.throw(err)
            except StopIteration:
                break
    print("After inner(), I do that.")

那么如果说我们将其换成python3中yield from模式，那么我么就会得到如下的代码

1
2
3
4
def outer2():
    print("Before inner(), I do this.")
    yield from inner()
    print("After inner(), I do that.")

我们可以发现内外层的行为非常一致，消息一层一层的传递，外层对内层的调度，yied from就封装了消息传递和调度作用