深度優先和廣度優先的Python實現
#coding=utf-8 class Gragh(): def __init__(self,nodes,sides): ''' nodes 表示點 sides 表示邊 ''' # self.sequense是字典，key是點，value是與key相連接的點 self.sequense = {} # self.side是臨時變數，主要用於保存與指定點相連接的點 self.side=[] for node in nodes: for side in sides: u,v=side # 指定點與另一個點在同一個邊中，則說明這個點與指定點是相連接的點，則需要將這個點放到self.side中 if node ==u: self.side.append(v) elif node == v: self.side.append(u) self.sequense[node] = self.side self.side=[] #print self.sequense ''' # Depth-First-Search 深度優先演算法，是一種用於遍歷或搜索樹或圖的演算法。沿著樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。 當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。 這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點， 則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜索。 ''' def DFS(self,node0): #queue本質上是堆棧，用來存放需要進行遍歷的數據 #order裡面存放的是具體的訪問路徑 queue,order=[],[] #首先將初始遍歷的節點放到queue中，表示將要從這個點開始遍歷 queue.append(node0) while queue: #從queue中pop出點v，然後從v點開始遍歷了，所以可以將這個點pop出，然後將其放入order中 #這裡才是最有用的地方，pop（）表示彈出棧頂，由於下面的for循環不斷的訪問子節點，並將子節點壓入堆棧， #也就保證了每次的棧頂彈出的順序是下面的節點 v = queue.pop() order.append(v) #這裡開始遍歷v的子節點 for w in self.sequense[v]: #w既不屬於queue也不屬於order，意味著這個點沒被訪問過，所以講起放到queue中，然後後續進行訪問 if w not in order and w not in queue: queue.append(w) return order ''' readth-First-Search BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。 廣度優先搜索的實現一般採用open-closed表。 ''' def BFS(self,node0): #queue本質上是堆棧，用來存放需要進行遍歷的數據 #order裡面存放的是具體的訪問路徑 queue,order = [],[] #首先將初始遍歷的節點放到queue中，表示將要從這個點開始遍歷 # 由於是廣度優先，也就是先訪問初始節點的所有的子節點，所以可以 queue.append(node0) order.append(node0) while queue: #queue.pop(0)意味著是隊列的方式出元素，就是先進先出，而下面的for循環將節點v的所有子節點 #放到queue中，所以queue.pop(0)就實現了每次訪問都是先將元素的子節點訪問完畢，而不是優先葉子節點 v = queue.pop(0) for w in self.sequense[v]: if w not in order: # 這裡可以直接order.append(w) 因為廣度優先就是先訪問節點的所有下級子節點，所以可以 # 將self.sequense[v]的值直接全部先給到order order.append(w) queue.append(w) return order def main(): nodes = [i+1 for i in xrange(8)] sides=[(1, 2), (1, 3), (2, 4), (2, 5), (4, 8), (5, 8), (3, 6), (3, 7), (6, 7)] G = Gragh(nodes,sides) print G.DFS(1) print G.BFS(1) print G.DFS1(1) if __name__ == "__main__": main()
