廣度優先遍歷-bfs

顧名思義，bfs老是先訪問完同一層的結點，而後才繼續訪問下一層結點，它最有用的性質是能夠遍歷一次就生成中心結點到所遍歷結點的最短路徑，這一點在求無權圖的最短路徑時很是有用。廣度優先遍歷的核心思想很是簡單，用python實現起來也就十來行代碼。下面就是超精簡的實現，用來理解核心思想足夠了：python

import Queue

def bfs(adj, start):
    visited = set()
    q = Queue.Queue()
    q.put(start)
    while not q.empty():
        u = q.get()
        print(u)
        for v in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                q.put(v)


graph = {1: [4, 2], 2: [3, 4], 3: [4], 4: [5]}
bfs(graph, 1)

上面的代碼：算法

1 建立一個隊列，遍歷的起始點放入隊列app

2 從隊列中取出一個元素，打印它，並將其未訪問過的子結點放到隊列中函數

3 重複2，直至隊列空佈局

時間複雜度：基本與圖的規模成線性關係了，比起圖的其它算法動不動就O(n^2)的複雜度它算是至關良心了code

空間複雜度：咱們看到程序中使用了一個隊列，這個隊列會在保存一層的結點，當圖規模很大時佔用內存仍是至關可觀的了，因此通常會加上一些條件，好比遍歷到第N層就中止blog

關於圖的理解的一個技巧

上面提到，bfs遍歷會由近及遠，同一層會先遍歷完。這裏隨便提一個關於圖的展現問題，或者說當你拿到一個圖，當你要對它進行分析時，這個圖在你的腦海裏會一個什麼形態呢？比較一下下面兩種形態，你以爲哪種更加清晰？遞歸

其實你仔細看，左右兩張圖其實數據是同樣的，只是佈局不同罷了，上面的圖使用了一種無規律凌亂的佈局，而下面假設出了一箇中心點，將與它直接相連的結點放在第一層上，與它距離爲2的結點放在第二層了，這樣會有什麼好處呢？好處就是這樣佈局後邊只會在相鄰層或者同一層間的結點間相連，這樣就不會出現很長或者交叉的邊了，整個圖會感受有序得多，在思考圖的一些性質的時候也會清晰得多。索引

回過頭來，這種佈局不說是bfs造成的嗎。隊列

深度優先遍歷

深度優先遍歷算法dfs通俗的說就是「順着起點往下走，直到無路可走就退回去找下一條路徑，直到走完全部的結點」。這裏的「往下走」主是優先遍歷結點的子結點。bfs與dfs均可以完成圖的遍歷。dfs經常使用到爬蟲中，下面是最精簡的代碼：

def dfs(adj, start):
    visited = set()
    stack = [[start, 0]]
    while stack:
        (v, next_child_idx) = stack[-1]
        if (v not in adj) or (next_child_idx >= len(adj[v])):
            stack.pop()
            continue
        next_child = adj[v][next_child_idx]
        stack[-1][1] += 1
        if next_child in visited:
            continue
        print(next_child)
        visited.add(next_child)
        stack.append([next_child, 0])


graph = {1: [4, 2], 2: [3, 4], 3: [4], 4: [5]}
dfs(graph, 1)

上面的代碼是dfs的非遞歸實現，其實遞歸的代碼更簡單，可是我以爲使用了函數的遞歸調用隱含了對棧的使用可是卻沒有明確出來，這樣不太利於對dfs核心思想的理解，因此這裏反而選擇了更復雜的非遞歸實現。

整個程序藉助了一個棧，因爲python沒有直接的實現棧，這裏使用了list來模擬，入棧就是向列表中append一個元素，出棧就是取列表最後一個元素而後pop將最後一個元素刪除

下面來分析實現過程，仍是按以前的那句話「順着起點往下走，直到無路可走就退回去找下一條路徑，直到走完全部的結點」，整個程序都蘊含在這句話中：

首次是「順着起點往下走」中的起點固然就是函數傳進來的參數start，第三行中咱們把起點放到了棧中，此時棧就是初始狀態，其中就只有一個元素即起點。那麼棧中元素表示的語義是：下一次將訪問的結點，沒錯就這麼簡單，那麼爲何咱們一個結點和一個索引來表示呢？理由是這樣的，因爲咱們使用鄰接表來表示圖，那麼要表示一個結點表能夠用<這個結點的父結點、這個結是父結點的第幾個子結點>來決定，至於爲何要這麼表示，就仍是前面說的：由這們這裏使用的圖的存儲方式-鄰接表決定了，由於這樣咱們取第N個兄弟結點要容易了。由於鄰接表中用list來表示一個結點的全部子結點，咱們就用一個整數的索引值來保存下次要訪問的子結點的list的下標，當這個下標超過子結點list的長度時意味着訪問完全部子結點。

接着，「往下走」，看這句：next_child = adj[v][next_child_idx]就是咱們在這個while循環中每次訪問的都是一個子結點，訪問完當前結點後stack.append([next_child, 0])將這個結點放到棧中，意思是下次就訪問這個結點的子結點，這樣就每次都是往下了。

「直到無路可走」，在程序中的體現就是 if (v not in adj) or (next_child_idx >= len(adj[v])):，棧頂元素表示即將要訪問的結點的父結點及其是父結點的第N個子結點（有點繞），這裏的意思是若是這個父結點都沒有子結點了或者是咱們想要訪問第N個子結點可是父結點並無這麼多子結點，表示已經訪問完了一個父結點的全部子結點了。

接着「就退回去找下一條路徑」中的「退回去」，怎麼退回去，很簡單將棧頂元素彈出，新的棧頂元素就是它的父結點，那麼就是退回去了，「去找下一條路徑」就是彈出棧頂後下一次while中會沿着父結點繼續探索，也就是去找下一條路徑了。

最後「直到走完全部的結點「固然就是棧爲空了，棧爲空表示已經回退到起點，即全部結點已經訪問完了，整個算法結束。