更新中。。。

第二章

2.2.2 交通規(guī)則

幾種常見的漸近運(yùn)行時(shí)間實(shí)例

2.2.4 三種重要情況

這里有一個(gè) else 的例子，用法并不常見，下面的代碼中，如果循環(huán)，沒有被 break 語(yǔ)句提前終止，那么將會(huì)執(zhí)行 else分支！

def sort_w_check(seq):
    n = len(seq)
    for i in range(n-1):
        if seq[i] > seq[i+1]:
            break
    else:
        return

排序算法的三種情況：

1. 最好情況
2. 最壞情況
3. 平均情況

2.3 圖與樹的實(shí)現(xiàn)

圖結(jié)構(gòu)(graph) 算法學(xué)中最強(qiáng)大框架之一。在許多情況下，我們都可以把一個(gè)問(wèn)題抽象為一個(gè)圖，如果能抽象為一個(gè)圖的話，那么該問(wèn)題至少已經(jīng)接近解決方案了。如果問(wèn)題實(shí)例可以用樹(tree)詮釋的話，那么我們基本上已經(jīng)擁有了一個(gè)真正有效的的解決方案了。
下面是一些關(guān)于圖的術(shù)語(yǔ)：

• 圖 G = (V,E) 通常由一組節(jié)點(diǎn) V 及節(jié)點(diǎn)間的邊 E 共同組成。如果這些邊有方向，就稱其為有向圖。
• 節(jié)點(diǎn)之間通過(guò)邊來(lái)實(shí)現(xiàn)彼此相連的。而這些邊其實(shí)就是節(jié)點(diǎn) v 與其鄰居之間的關(guān)系。
• G = (V，E] 的子圖結(jié)構(gòu)將由 V 和 E 的子集共同組成。在 G 中，每一條路徑(path)是一個(gè)子圖結(jié)構(gòu)，它們本質(zhì)上都是一些由多個(gè)節(jié)點(diǎn)串聯(lián)而成的邊線序列。環(huán)路(cycle)的定義與路徑基本相同，只不過(guò)它的最后一條邊所連接的末節(jié)點(diǎn)同是是它的首節(jié)點(diǎn)。
• 如果我們將圖 G 中的邊與某種權(quán)值聯(lián)系在一起，G 就成了一種加權(quán)圖。在加權(quán)圖中，一條路徑或環(huán)路的長(zhǎng)度等于各邊上的權(quán)值之和，對(duì)非加權(quán)圖來(lái)說(shuō)，就直接等于該圖的邊數(shù)。
• 森林 (forest) 可以被認(rèn)為是一個(gè)無(wú)環(huán)路圖，而這樣的連通圖就是一棵樹。換言之，森林就是由一棵或多棵樹構(gòu)成的。

2.3.1 鄰接列表及其類似結(jié)構(gòu)

對(duì)于圖結(jié)構(gòu)的實(shí)現(xiàn)來(lái)說(shuō)，鄰接列表是最直觀的方式之一。
接下來(lái)，我們就要用數(shù)據(jù)結(jié)構(gòu)來(lái)表示圖。

示例圖

圖 2-3

清單 2-1 簡(jiǎn)單明了的鄰接集表示法

a, b, c, d, e, f, g, h = range(8)
N = [
    {b, c, d, e, f},     # a 的所有出邊，下同
    {c, e},              # b 
    u0z1t8os,                 # c
    {e},                 # d
    {f},                 # e 
    {c, g, h},           # f
    {f, h},              # g
    {f, g}               # h
]

In [9]: b in N[a]  # b 是 a 的鄰居
Out[9]: True

In [10]: len(N[f]) # f 有3個(gè)鄰居
Out[10]: 3

清單 2-2 鄰接列表

a, b, c, d, e, f, g, h = range(8)
N = [
    [b, c, d, e, f],     # a 的所有出邊，下同
    [c, e],              # b 
    [d],                 # c
    [e],                 # d
    [f],                 # e 
    [c, g, h],           # f
    [f, h],              # g
    [f, g]               # h
]

清單 2-3 加權(quán)鄰接字典

a, b, c, d, e, f, g, h = range(8)
N = [
    {b:2, c:1, d:3, e:9, f:4},     # a 的所有出邊及權(quán)值，下同
    {c:4, e:3},              # b 
    {d:8},                   # c
    {e:7},                   # d
    {f:5},                   # e 
    {c:2, g:2, h:2},         # f
    {f:1, h:6},              # g
    {f:g, g:8}               # h
]

以上三種鄰接結(jié)構(gòu)的主容器都屬于列表類型，都是以節(jié)點(diǎn)編號(hào)為索引值。dict 更靈活。

2.3.2 鄰接矩陣

圖的另一種表示方法就是鄰接矩陣了。它的不同之處在于，它不再列出每個(gè)節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)，而是將所有可能的鄰居位置排一行(也就是一個(gè)數(shù)組，用于對(duì)應(yīng)圖中每一個(gè)節(jié)點(diǎn))，然后使用某種值(True or False)來(lái)表示其是否為當(dāng)前節(jié)點(diǎn)的鄰居。與上面一樣，依然使用最簡(jiǎn)單的列表來(lái)表示。同是為了讓矩陣有較好的可讀性，我們將使用１和０來(lái)表示真值。且節(jié)點(diǎn)的編號(hào)從0開始。

清單　2-5

a, b, c, d, e, f, g, h = range(8)
#     a  b  c  d  e  f  g  h
N = [[0, 1, 1, 1, 1, 1, 0, 0],   # a
    [0, 0, 1, 0, 1, 0, 0, 0],    # b
    [0, 0, 0, 1, 0, 0, 0, 0],    # c
    [0, 0, 0, 0, 1, 0, 0, 0],    # d
    [0, 0, 0, 0, 0, 1, 0, 0],    # e
    [0, 0, 1, 0, 0, 0, 1, 1],    # f                   
    [0, 0, 0, 0, 0, 1, 0, 1],    # g
    [0, 0, 0, 0, 0, 1, 1, 0]]    # h

同是，其使用方法也略有不同^[1]，這里檢查的不是 b 是否在 N[a]中，而是檢查矩陣單元 N[a][b] 是否為真。同樣，要獲取相關(guān)節(jié)點(diǎn)的鄰居數(shù)，改用 sum 函數(shù)即可，因?yàn)椋行械拈L(zhǎng)度是相等的！

In [6]: N[a][b]
Out[6]: 1

In [7]: sum(N[f])
Out[7]: 3

特點(diǎn)：

1. 在不允許自循環(huán)的狀態(tài)下，對(duì)角線上的值全為假。
2. 無(wú)向圖矩陣是一個(gè)對(duì)稱矩陣

加權(quán)處理：

1. 只需在存儲(chǔ)真值的地方直接存儲(chǔ)相應(yīng)權(quán)值即可。
2. 出于實(shí)踐因素考慮，通常把實(shí)際不存在的邊的權(quán)值設(shè)為無(wú)窮大(float('inf'))

清單 2-6 對(duì)不存在的邊賦予無(wú)限大權(quán)值的加權(quán)矩陣

a, b, c, d, e, f, g, h = range(8)
inf = float('inf')
W = [[  0,   2,   1,   3,   9,   4, inf, inf], # a
     [inf,   0,   4, inf,   3, inf, inf, inf], # b
     [inf, inf,   0,   8, inf, inf, inf, inf], # c
     [inf, inf, inf,   0,   7, inf, inf, inf], # d
     [inf, inf, inf, inf,   0,   5, inf, inf], # e
     [inf, inf,   2, inf, inf,   0,   2,   2], # f
     [inf, inf, inf, inf, inf,   1,   0,   6], # g
     [inf, inf, inf, inf, inf,   9,   8,   0]] # h

加權(quán)矩陣使得相關(guān)加權(quán)邊的訪問(wèn)變得容易，但需要對(duì)相關(guān)無(wú)窮大值進(jìn)行檢測(cè)

In [23]: W[a][b]
Out[23]: 2

In [24]: W[c][e] < inf
Out[24]: True

In [25]: sum(1 for w in W[a] if w < inf) - 1
Out[25]: 5

這里減去 1 是排除掉對(duì)角線的 0

2.3.3 樹的實(shí)現(xiàn)

一般來(lái)說(shuō)，可以表示成圖的方法都能用來(lái)表示樹，樹是圖的特殊情況。
最簡(jiǎn)單的樹： 帶根樹結(jié)構(gòu)

樹

此樹的代碼表示：

In [35]: T = [["a", "b"], ["c"], ["d", ["e", "f"]]]

In [36]: T[0][1]
Out[36]: 'b'

In [37]: T[2][1][0]
Out[37]: 'e'

清單 2-7 二叉樹類

class Tree:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        
        
In [39]: t = Tree(Tree('a', 'b'), Tree('c', 'd'))

In [40]: t.right.left
Out[40]: 'c'

上例可描述為下圖：

二叉樹類

清單 2-8 多路搜索樹
對(duì)于沒有 list內(nèi)置類型的語(yǔ)言，可以采用“先子節(jié)點(diǎn)，后兄弟節(jié)點(diǎn)的”的表示法！

class Tree:
    def __init__(self, kids, next=None):
        self.kids = self.val = kids
        self.next = next
        
這里的 val 只是為相關(guān)的值提供更具描述性的名稱，可以自行更換其他你喜歡的。       
In [62]: t = Tree(Tree('a', Tree('b', Tree('c', Tree('d')))))
In [64]: t.kids.next.next.val
Out[64]: 'c'
In [77]: t.kids.val 
Out[77]: 'a'
In [47]: t.kids.kids
Out[47]: 'a'
In [69]: t.kids.next.val
Out[69]: 'b'
In [72]: t.kids.next.next.next.val
Out[72]: 'd'

Bunch模式：

class Bunch(dict):
    def __int__(self, *args, **kwds):
        super(Bunch, self).__init__(*args, **kwds)
        self.__dict__ = self
        

In [56]: t = T(left=T(left='a', right='b'), right=T(left='c'))

In [57]: t
Out[57]: {'left': {'left': 'a', 'right': 'b'}, 'right': {'left': 'c'}}

In [60]: t['left']['left']
Out[60]: 'a'

In [61]: 'left' in t['right']
Out[61]: True

In [62]: 'right' in t['right']
Out[62]: False

用處：

1. 可以以命令行參數(shù)的形式創(chuàng)建相關(guān)對(duì)象并設(shè)置屬性。
2. 繼承自 dict 可以自然獲得大量相關(guān)的內(nèi)容。

2.3.4 多種表示法

圖表示法的草見解：

1. 圖可以由鄰接列表和鄰接矩陣兩種方法表示。
2. 鄰接矩陣速度快，但消耗資源多。二者的選擇取決于哪種資源更重要。

2.4 請(qǐng)?zhí)岱篮诤凶?/h3>

“黑盒子”： 項(xiàng)目中非自己所寫的依賴。

提防陷阱的方法：

• 性能很重要時(shí)，要著重于實(shí)際分析而不是直覺。
• 正確性很重要時(shí)，使用不同的方法進(jìn)行多次計(jì)算并交由不同的程序員編寫

2.4.1 隱形平方級(jí)操作

In [63]: from random import randrange

In [64]: L = [randrange(10000) for i in range(1000)]

In [65]: 42 in L
Out[65]: False

In [66]: S = set(L)

In [67]: 42 in S
Out[67]: False

在 list 上構(gòu)建 set貌似毫無(wú)意義。但如果是下面兩中情況就會(huì)很適用：

1. 執(zhí)行多次查詢時(shí)，list 是線性級(jí)，而 set 是常數(shù)級(jí)的。
2. 向其中添加新值時(shí)，list 是平方級(jí)，而 set 是線性級(jí)！

res = []
for lst in lists:
    res.extend(lst)

上式要優(yōu)于

>>> lists = [[1, 2], [3, 4], [5, 6]]
>>> sum(lists, [])

2.4.2 浮點(diǎn)數(shù)的麻煩

不要對(duì)浮點(diǎn)數(shù)進(jìn)行比較

第三章 計(jì)數(shù)初步

3.4.2

遞歸調(diào)用的一般形式：T(n) = a.T(g(n)) + f(n)。其中

a: 遞歸調(diào)用數(shù)量
g(n): 遞歸調(diào)用過(guò)程中，所要解決的子問(wèn)題大小。
f(n): 函數(shù)的額外操作

                     一些基本遞歸式的解決方案及其實(shí)例

如遇到其他的遞歸式，可以嘗試向如上基本式化簡(jiǎn)。來(lái)求得其復(fù)雜度！

3.5

侏儒排序

def gnome_sort(seq):
    if len(seq) <= 1:
        return seq
    i = 1
    while i < len(seq):
        if i == 0 or seq[i-1] <= seq[i]:
            i += 1
        else:
            seq[i], seq[i-1] = seq[i-1], seq[i]
            i -= 1
    return seq
    
if __name__ == '__main__':
    seq = [5, 3, 6, 9, 8, 2]
    print(gnome_sort(seq))

應(yīng)該不用做過(guò)多解釋！使用Python Tutor可以看到此排序執(zhí)行步數(shù)是74次。反正是沒有分治法的歸并排序速度快。而且在最壞情況下，其復(fù)雜度為O($n^2$)

In [7]: def mergesort(seq):
   ...:     mid = len(seq)//2
   ...:     lft = seq[:mid]
   ...:     rgt = seq[mid:]
   ...:     if len(lft) > 1:
   ...:         lft = mergesort(lft)
   ...:     if len(rgt) > 1:    
   ...:         rgt = mergesort(rgt)
   ...:
   ...:     res = []
   ...:     while lft and rgt:
   ...:         if lft[-1] >= rgt[-1]:
   ...:             res.append(lft.pop())
   ...:         else: 
   ...:             res.append(rgt.pop())
   ...:             
   ...:     res.reverse()
   ...:     return (lft or rgt) + res

第四章 歸納、遞歸及歸簡(jiǎn)

• 歸簡(jiǎn)法指的是將某一問(wèn)題轉(zhuǎn)化成另一個(gè)問(wèn)題。
• 歸納法則被用于證明某個(gè)語(yǔ)句對(duì)于某種大型對(duì)象類是否成立！
• 遞歸法則主要被用與函數(shù)自我調(diào)用時(shí)。

4.1 哦，這其實(shí)很簡(jiǎn)單

歸簡(jiǎn)

假設(shè)從一個(gè)數(shù)字列表中找出兩個(gè)彼此相近但不相等的數(shù)。

In [80]: from random import randrange

In [123]: seq = [randrange(10**10) for i in range(100)]

In [124]: dd = float("inf")

In [125]: for x in seq:
     ...:     for y in seq:
     ...:         if x == y: continue
     ...:         d = abs(x-y)
     ...:         if d < dd:
     ...:             xx, yy, dd = x, y, d
     ...:             

In [126]: xx, yy
Out[126]: (9733435205, 9734468535)

兩層嵌套的循環(huán)，都對(duì)seq遍歷，明顯的平方級(jí)操作。接下來(lái)我們就優(yōu)化下代碼，先把列表排序，絕對(duì)值最小的兩個(gè)數(shù)必然是相鄰。于是代碼如下。

In [87]: seq.sort()

In [124]: dd = float("inf")

In [125]: for x in seq:
     ...:     for y in seq:
     ...:         if x == y: continue
     ...:         d = abs(x-y)
     ...:         if d < dd:
     ...:             xx, yy, dd = x, y, d
     ...:             

In [126]: xx, yy
Out[126]: (9733435205, 9734468535)

這樣算法更快了，但解決方案照舊！

歸納法證明了遞歸法的適用性，而遞歸法則是直接實(shí)現(xiàn)歸納法思維的一種簡(jiǎn)單方式。

4.3

再來(lái)兩個(gè)排序。(雖然以前寫過(guò)多次。)

1. 插入排序迭代版

def ins_sort(seq):
    if len(seq) <= 1:
        return seq
    for i in range(1, len(seq)):
        j = i
        while j > 0 and seq[j-1] > seq[j]:
            seq[j], seq[j-1] = seq[j-1], seq[j]
            j -= 1
    return seq
    
if __name__ == "__main__":
    seq = [5, 3, 6, 9, 8, 2]
    print(ins_sort(seq))

遞歸版插入排序

def ins_sort_rec(seq, i):
    if i == 0: 
        return seq
    j = i
    while j > 0 and seq[j-1] > seq[j]:
        seq[j], seq[j-1] = seq[j-1], seq[j]
        j -= 1
    return ins_sort_rec(seq, i-1)
    
if __name__ == "__main__":
    seq = [5, 3, 6, 9, 8, 2]
    print(ins_sort_rec(seq, 5))

2. 選擇排序

def sel_sort(seq):
    for i in range(len(seq)-1, 0, -1):
        max_j = i # 預(yù)設(shè)最大索引 max_j
        for j in range(i): 
            if seq[j] > seq[max_j]:
                max_j = j # 實(shí)際最大的 max_j
        seq[i], seq[max_j] = seq[max_j], seq[i] # 交換最大值
    return seq

if __name__ == "__main__":
    seq = [5, 3, 6, 9, 8, 2]
    print(sel_sort(seq))

4~6行類似尋找一組數(shù)字中的最大值。這里是找最大的索引值！
遞歸版

def sel_sort_rec(seq, i):
    if i == 0: return seq
    max_j = i
    for j in range(i):
        if seq[j] > seq[max_j]:
            max_j = j
    seq[i], seq[max_j] = seq[max_j], seq[i]
    return sel_sort_rec(seq, i-1)
    
if __name__ == "__main__":
    seq = [5, 3, 6, 9, 8, 2]
    print(sel_sort_rec(seq, 5))

4.4 基于歸納法(與遞歸法)的設(shè)計(jì)

4.4.1 尋找最大排列

有 a, b, c, d, e, f, g, h 八個(gè)人。在電影院更換座位的問(wèn)題！

圖 4-4

箭頭指向就是他們想要的座位。我們可以從圖中找出其映射關(guān)系。這里就是各元素(0, ... n-1)與其位置(0, ... n-1)之間的關(guān)聯(lián)性。我們可以用一個(gè)簡(jiǎn)單的列表實(shí)現(xiàn)。(各元素選擇的座位作為其值。)

>>> M = [2, 2, 0, 5, 3, 5, 7, 4]

接下來(lái)就可以簡(jiǎn)單的實(shí)現(xiàn)下了。

• 尋找最大排列問(wèn)題的遞歸思路的樸素解決方案

In [8]: def naive_max_perm(M, A=None):
   ...:     if A is None:
   ...:         A = set(range(len(M)))
   ...:     if len(A) == 1: 
   ...:         return A
   ...:     B = set(M[i] for i in A)
   ...:     C = A - B
   ...:     if C:
   ...:         A.remove(C.pop())
   ...:         return naive_max_perm(M, A)
   ...:     return A

In [10]: naive_max_perm(M)
Out[10]: {0, 2, 5}

這段代碼中，函數(shù)naive_max_perm收到一個(gè)代表剩余人數(shù)的集合A， 并創(chuàng)建一個(gè)被指向座位的集合B。然后此函數(shù)會(huì)找出并刪除集合A中某個(gè)不屬于集合B的元素。之后，遞歸解決剩余人員。直至 A = B。
此程序是平方級(jí)操作，最浪費(fèi)的操作就是每次遞歸時(shí)集合B都要重復(fù)創(chuàng)建。為此能解決這個(gè)問(wèn)題，我們也就可以將其復(fù)雜度變成線性級(jí)了！

我們可以為各元素設(shè)置一個(gè)計(jì)數(shù)器，當(dāng)有指向x座位的人被淘汰時(shí)，就遞減該座位的計(jì)數(shù)器，并當(dāng)x的計(jì)數(shù)器為0時(shí)，將編號(hào)為x的人和座位一同淘汰掉即可。

• 迭代版實(shí)現(xiàn)

def max_perm(M):
    n = len(M)
    A = set(range(n))
    count = [0]*n
    for i in M:
        count[i] += 1 # 相當(dāng)于 count = collections.Counter(M)
    Q = [i for i in A if count[i] == 0]
    while Q:
        i = Q.pop()
        A.remove(i)
        j = M[i]
        count[j] -= 1
        if count[j] == 0:
            Q.append(j)
    return A
        

計(jì)數(shù)排序

from collections import defaultdict

def count_sort(seq, key=lambda x: x):
    L, D = [], defaultdict(list)
    for i in seq:
        D[key(i)].append(i) 
        # D -- {0: [0], 2: [2, 2], 3: [3], 4: [4], 5: [5, 5], 7: [7]})
        #這里順序恰巧是排序好的，僅僅是巧合而已
    for key in range(min(D), max(D)+1):
        L.extend(D[key]) # 根據(jù)key來(lái)排序，而key的大小和value是對(duì)應(yīng)的。當(dāng)key不在D中時(shí)，返回 []
                       # key的值從小到大，不受D中元素的順序影響
    return L
    
M = [2, 2, 0, 5, 3, 5, 7, 4]
print(count_sort(M))

defaultdict 簡(jiǎn)化了處理不存在的鍵的場(chǎng)景。

w = ['a', 'b', 'w', 'r']
d = {}
for i in w:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
        
# use defaultdict

d = defaultdict()
for i in w:
    d[i] += 1

下面是python官方文檔的例子。

>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)   
>>> for k, v in s:         
...     d[k].append(v)   
...
>>> d.items()
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

4.4.2 明星問(wèn)題

所謂明星簡(jiǎn)單說(shuō): 就是別人都認(rèn)識(shí)ta,而ta不認(rèn)識(shí)別人。此算法有以下幾種用處：

1. 處理 Linux 中各種軟件包的依賴問(wèn)題！
2. 多線程的死鎖問(wèn)題

def naive_celeb(G): # 尋找 G 中的明星, G 是一個(gè)二維數(shù)組.
    n = len(G)
    for u in range(n): # 遍歷每個(gè)數(shù)組
        for v in range(n):  # 遍歷數(shù)組中的每個(gè)元素
            if u == v: continue # 相同的人,跳過(guò)
            if G[u][v]: break   # 明星認(rèn)識(shí)路人, 結(jié)束此次循環(huán)
            if not G[v][u]: break  # 路人不認(rèn)識(shí)明星, 結(jié)束
        else:
            return u               # u 是明星
    return None

可以很明顯的看出, naive_celeb 函數(shù)的兩次循環(huán)致使此程序的復(fù)雜度 O($n^2$).現(xiàn)在我們就要使用歸簡(jiǎn)法將問(wèn)題的規(guī)模從 n 歸簡(jiǎn)到 n-1,其實(shí),對(duì)每個(gè) u 都進(jìn)行遍歷是多余的,因?yàn)榉敲餍钦J(rèn)識(shí)不需再往下進(jìn)行了,所以要做的就是排除掉非明星人士即可.下面就要解決這個(gè)問(wèn)題,將其變?yōu)橐粋€(gè)線性級(jí)的算法.

def celeb(G):
    n = len(G)
    u, v = 0, 1           # 假設(shè) u 是明星
    for c in range(2, n+1):
        if G[u][v]: u = c # u 認(rèn)識(shí) v,說(shuō)明 u 不是明星,循環(huán)變量 c 賦值給 u,遍歷下一組.
        else:       v = c # u 是明星, c 賦值給 v 遍歷G(u)中的下一個(gè)元素
    if u == n:      c = v # 最后一次遍歷后,u == n 說(shuō)明 u 不是明星,則 v 是.
    else:           c = u # u是明星,這是的 c 不是循環(huán)變量了.只是一個(gè)中間值,可以換成其他已聲明的變量
    
    for v in range(n):    
        if c == v: continue   # 同一個(gè)人, 跳過(guò)
        if G[c][v]: break     # 明星 c 認(rèn)識(shí)路人, 卡
        if not G[v][c]: break # 路人不識(shí)明星, 卡
    else:
        return c
    return None

接下來(lái),就要構(gòu)建一個(gè)隨機(jī)圖,來(lái)驗(yàn)證函數(shù)的正確與否!

In [273]: from random import randrange
     ...: n = 100
     ...: G = [[randrange(2) for i in range(n)] for _ in range(n)]
     ...: x = randrange(n) # 設(shè)置一個(gè)明星 x
     ...: for i in range(n):
     ...:     G[i][x] = True # 所有人都認(rèn)識(shí)明星 x
     ...:     G[x][i] = False # 明星 x 不認(rèn)識(shí)任何人 
     ...:     

In [274]: x
Out[274]: 19

In [275]: naive_celeb(G)
Out[275]: 19

In [276]: celeb(G)
Out[276]: 19

4.4.3 拓?fù)渑判騿?wèn)題 #看不太懂， mark

定義:

在圖論中，由一個(gè)有向無(wú)環(huán)圖的頂點(diǎn)組成的序列，當(dāng)且僅當(dāng)滿足下列條件時(shí)，稱為該圖的一個(gè)拓?fù)渑判?/a>（英語(yǔ)：Topological sorting）。

1. 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次；
2. 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。

DAG

• 解決任務(wù)之間的依賴關(guān)系

當(dāng)我使用 Debian 安裝軟件時(shí),系統(tǒng)會(huì)提示缺少某個(gè)或某些組件，需要安裝它們。對(duì)于這一類工作，相關(guān)組件必須按照一定的拓?fù)漤樞騺?lái)安裝！接下來(lái)就實(shí)現(xiàn)下此算法。

清單 4-9 樸素版拓?fù)渑判蚍?/p>

def naive_topsort(G, S=None):
    if S is None: S = set(G)          # all the nodes
    if len(S) == 1:                   # single node， return
        return list(S)
    v = S.pop()
    seq = naive_topsort(G, S)
    min_i = 0
    for i, u in enumerate(seq):
        if v in G(u):
            min_i = i + 1
    seq.insert(min_i, v)
    return seq

這是一個(gè)平方級(jí)算法，當(dāng)每次任意選擇一個(gè)節(jié)點(diǎn)時(shí)，其都要檢查其余節(jié)點(diǎn)是否符合后續(xù)遞歸調(diào)用（線性操作）。因此，我們只要在遞歸調(diào)用之前找出被移除的節(jié)點(diǎn)即可。

def topsort(G):
    count = dict((u, 0) for u in G)
    for u in G:
        for v in G(u):
            count[v] += 1
    Q = [u for u in G if count[u] == 1]
    S = []
    while Q:
        u = Q.pop()
        S.append(u)
        for v in G[u]:
            count[v] -= 1
            if count[v] == 0:
                Q.append(v)
    return S

第五章 遍歷：算法學(xué)中的萬(wàn)能鑰匙

清單 5-1 遍歷一個(gè)表示為鄰接集的圖結(jié)構(gòu)的連通分量

def walk(G, s, S=set()):        # G 是一鄰接集的字典表示
    P, Q = dict(), set()
    P[s] = None
    Q.add(s)
    while Q:
        u = Q.pop()
        for v in G[u].difference(P, S):   # v 是 set 對(duì)象
            Q.add(v)
            P[v] = u
    return P

我們初開始可以找一個(gè)出發(fā)點(diǎn)作為根節(jié)點(diǎn)，然后從此節(jié)點(diǎn)開始走，我們可以往左走，可以往右走，隨你。當(dāng)我們走到一個(gè)死胡同時(shí)，就要進(jìn)行回溯。

walk 函數(shù)所遍歷的只是單個(gè)分量，下面這個(gè)該圖的所有連通分量。
測(cè)試一下：

In [16]: G2 = {
    ...:     0:{1, 2},
    ...:     1:{1, 3},
    ...:     2:{2, 4},
    ...:     3:{0, 3},
    ...:     4:{4, 5},
    ...:     5:{2, 3}
    ...:     }
    
In [26]: walk(G2, 1)
Out[26]: {0: 3, 1: None, 2: 0, 3: 1, 4: 2, 5: 4}

In [27]: walk(G2, 0)
Out[27]: {0: None, 1: 0, 2: 0, 3: 1, 4: 2, 5: 4}

清單 5-2 找出圖的連通分量

def component(G):
    comp = []
    seen = set()
    for u in G:
        C = walk(G, u)
        seen.update(C)
        comp.append(C)
    return comp 

測(cè)試一下：

In [18]: component(G2)
Out[18]: 
[{0: None, 1: 0, 2: 0, 3: 1, 4: 2, 5: 4},
 {0: 3, 1: None, 2: 0, 3: 1, 4: 2, 5: 4},
 {0: 3, 1: 0, 2: None, 3: 5, 4: 2, 5: 4},
 {0: 3, 1: 0, 2: 0, 3: None, 4: 2, 5: 4},
 {0: 3, 1: 0, 2: 5, 3: 5, 4: None, 5: 4},
 {0: 3, 1: 0, 2: 5, 3: 5, 4: 2, 5: None}]

挺好的。

5.1 公園漫步

5.1.1 不允許出現(xiàn)環(huán)路

迷宮

遍歷一個(gè)沒有環(huán)路的迷宮，其基本結(jié)構(gòu)是一棵數(shù)。保持單手扶墻走就能遍歷整個(gè)迷宮。其迷宮只有一面內(nèi)墻，只要不出現(xiàn)環(huán)路，我們總能到達(dá)一個(gè)確定的地方。我們初開始可以找一個(gè)出發(fā)點(diǎn)作為根節(jié)點(diǎn)，然后從此節(jié)點(diǎn)開始走，我們可以往左走，可以往右走，隨你。當(dāng)我們走到一個(gè)死胡同時(shí)，就要進(jìn)行回溯。順著這樣的策略，我們就能探索到所有節(jié)點(diǎn)，而且每條通道都會(huì)經(jīng)過(guò)兩次。下面是一個(gè)最基本的的實(shí)現(xiàn)。
清單 5-3 遞歸的樹遍歷算法

def tree_walk(T, r):             # 從 r 開始遍歷
    for u in T[r]:               # 對(duì)于每一子節(jié)點(diǎn)...
        tree_walk(T, u)          # ...遍歷子樹

5.1.2 停止循環(huán)遍歷的方式

每次進(jìn)入或離開一個(gè)十字路口時(shí)留下一個(gè)標(biāo)志就行了。避免重復(fù)走同一條通道。下面是一個(gè) Tremaux 算法。所使用的是深度優(yōu)先搜索。(最基本最重要的遍歷策略之一)
清單 5-4 遞歸版的深度優(yōu)先搜索

def rec_dfs(G, s, S=None):
    if S is None:
        S = set()
    S.add(s)
    for u in G[s]:
        if u in S:
            continue
        rec_dfs(G, u, S)

下面將遞歸操作轉(zhuǎn)換成迭代版，以此來(lái)避免調(diào)用棧被塞滿帶來(lái)的問(wèn)題。
清單 5-5 迭代版深度優(yōu)先搜索

def iter_dfs(G, s):
    S, Q= set(), []
    Q.append(s)
    while Q:
        u = Q.pop()
        if u in S:               # 遍歷過(guò)的就跳過(guò)
            continue
        S.add(u)
        Q.extend(G[u])
        yield u

用圖2-3 的圖結(jié)構(gòu)測(cè)試一下測(cè)試看看

In [71]: a, b, c, d, e, f, g, h = range(8)
    ...: G = {
    ...:    a: [b, c, d, e, f],     # a 的所有出邊，下同
    ...:    b: [c, e],              # b 
    ...:    c: [d],                 # c
    ...:    d: [e],                 # d
    ...:    e: [f],                 # e 
    ...:    f: [c, g, h],           # f
    ...:    g: [f, h],              # g
    ...:    h: [f, g]               # h
    ...: }

In [73]: list(iter_dfs(G, 0))
Out[73]: [0, 5, 7, 6, 2, 3, 4, 1]

我們剛才是在一個(gè)有向圖上進(jìn)行的 DFS 。DFS或者其他遍歷算法都適用于有向圖上，但如果在有向圖上進(jìn)行遍歷時(shí)，就不能指望它探索所有的連通分量了。比如下面：

In [74]: list(iter_dfs(G, 1))
Out[74]: [1, 4, 5, 7, 6, 2, 3

因?yàn)?a 節(jié)點(diǎn)不存在入邊， 從 a 節(jié)點(diǎn)以外的任何一點(diǎn)出發(fā)都不能到達(dá) a 節(jié)點(diǎn)！但我們可以有以下三種方法來(lái)找出有向圖中的連通分量：

1. 將有向圖轉(zhuǎn)換為無(wú)向圖
2. 直接為圖中的所有邊添加反向邊
3. 選擇合適的起始節(jié)點(diǎn)

清單 5-6 通用性的圖遍歷函數(shù)

def traverse(G, s, qtype=set):
    S, Q = set(), qtype()
    Q.add(s)
    while Q:
        u = Q.pop()
        if u in S:
            continue
        S.add(u)
        for v in G[u]:
            Q.add(v)
        yield u

這里默認(rèn)類型為 set ，我們也可以將其輕松定義成 stack 類型。使用的是一個(gè)是 List 的 append 和 pop 方法來(lái)模棧。

class stack(list):
    add = list.append

測(cè)試下看看嘍：

In [82]: list(traverse(G, 0, stack))
Out[82]: [0, 5, 7, 6, 2, 3, 4, 1]

5.2

深度優(yōu)先的時(shí)間戳與拓?fù)渑判?/h4>

在 DFS 樹中，任意 u 節(jié)點(diǎn)下的所有節(jié)點(diǎn)都應(yīng)該在 u 被訪問(wèn)并完成回溯操作之間這段時(shí)間內(nèi)處理完成。為此，我們?yōu)榍鍐?5-6 的版本中的每個(gè)節(jié)點(diǎn)添加時(shí)間戳。

• d 代表它被探索的時(shí)間
• f 代表回溯的時(shí)間

def　dfs(G, s, d, f, S=None, t=0):
    if S is None:
        S = set()
    d[s] = t
    t += 1
    S.add(s)
    for u in G[s]:
        if u in S:
            continue
        t = dfs(G, u, d, f, S, t)
    f[s] = t
    t += 1
    return t        

我們還可以此 DFS 來(lái)進(jìn)行拓?fù)渑判?，根?jù)其遞減的完成時(shí)間對(duì)節(jié)點(diǎn)進(jìn)行排序。
清單 5-8

def dfs_topsort(G):
    S, res = set(), []
    def recurse(u):
        if u in S:
            return
        S.add(u)
        for v in G[u]:
            recurse(v)
        res.append(u)
    for u in G:
        recurse(u)
    res.reverse()
    return res

用 G 測(cè)試一下：

In [5]: G
Out[5]: 
{0: [1, 2, 3, 4, 5],
 1: [2, 4],
 2: [3],
 3: [4],
 4: [5],
 5: [2, 6, 7],
 6: [5, 7],
 7: [5, 6]}


In [14]: dfs_topsort(G)
Out[14]: [0, 1, 2, 3, 4, 5, 6, 7]

5.3

無(wú)限迷宮與最短(不加權(quán))路徑問(wèn)題

清單5-9
清單 5-10 廣度優(yōu)先搜索

def bfs(G, s):
    P, Q = {s: None}, deque([s])
    while Q:
        u = Q.popleft()
        for v in G[u]:
            if v in P:
                continue
            P[v] = u
            Q.append(v)
    return P

測(cè)試一下：

In [22]: from queue import deque
    ...: for i in range(8):
    ...:     print(bfs(G, i))
    ...:     
{0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 5, 7: 5}
{1: None, 2: 1, 4: 1, 3: 2, 5: 4, 6: 5, 7: 5}
{2: None, 3: 2, 4: 3, 5: 4, 6: 5, 7: 5}
{3: None, 4: 3, 5: 4, 2: 5, 6: 5, 7: 5}
{4: None, 5: 4, 2: 5, 6: 5, 7: 5, 3: 2}
{5: None, 2: 5, 6: 5, 7: 5, 3: 2, 4: 3}
{6: None, 5: 6, 7: 6, 2: 5, 3: 2, 4: 3}
{7: None, 5: 7, 6: 7, 2: 5, 3: 2, 4: 3}

5.4 強(qiáng)連通分量

5.5 本章小結(jié)

通常情況下，一個(gè)圖的遍歷過(guò)程主要包括：
維護(hù)一個(gè)用來(lái)存放待探索節(jié)點(diǎn)的 to-do 列表，并從中除去已訪問(wèn)的節(jié)點(diǎn)，從遍歷的起點(diǎn)開始，每次都訪問(wèn) (并除去) 其中一個(gè)節(jié)點(diǎn)，并將其鄰居節(jié)點(diǎn)加入到該列表中。在此列表中，項(xiàng)目的 (調(diào)度) 順序很大程度上決定了我們實(shí)現(xiàn)的遍歷類型。
比如：

• 采用 LIFO 隊(duì)列執(zhí)行的就是 DFS
• 采用 FIFO 隊(duì)列執(zhí)行的就是 BFS

第六章 分解、合并、解決

6.2 經(jīng)典分治算法

清單 6-1 分治語(yǔ)義的一種通用性實(shí)現(xiàn)

def divide_and_conquer(S, divide, combine):
    if len(S) == 1:
        return S
    L, R = divide(S)
    A = divide_and_conquer(L, divide, combine)
    B = divide_and_conquer(R, divide, combine)
    return combine(A, B)

6.3 折半搜索

清單 6-2 二分搜索樹的插入與搜索

class Node:
    lft = None
    rgt = None

    def __init__(self, key, val):
        self.key = key
        self.val = val


def insert(node, key, val):
    if node is None:
        return Node(key, val)
    if node.key == key:
        node.val = val
    elif node.key < key:
        node.rgt = insert(node.rgt, key, val)
    else:
        node.lft = insert(node.lft, key, val)


def search(node, key):
    if node is None:
        raise KeyError
    if node.key == key:
        return node.val
    elif node.key < key:
        return search(node.rgt, key)
    else:
        return search(node.lft, key)


class Tree:
    root = None
    def __setitem__(self, key, val):
        self.root = insert(self.root, key, val)
    def __getitem__(self, key):
        return search(self.root, key)
    def __contains__(self, key):
        try:
            search(self.root, key)
        except KeyError:
            return False
        return True

---

1. 請(qǐng)看清單 2-1 ?