圖論Graph Theory是CS里面相當重要的一個領域，也是非常博大精深的一塊拘泞。這里主要實現(xiàn)一些比較基礎的算法纷纫。
圖可以分為有向圖和無向圖，有權圖和無權圖陪腌。圖的基本表示方法有鄰接矩陣辱魁，鄰接鏈表。兩者可以互相轉換诗鸭，這里都用鄰接鏈表作為圖的表示染簇。
BFS/DFS
BFS和DFS是圖的遍歷的基礎算法，就是從某一個節(jié)點開始遍歷整個圖强岸。對圖的有向性和有權性并沒有要求锻弓，對無向圖可視為每條邊都是雙向的。
簡而言之蝌箍，BFS就是維持一個queue青灼，每次把節(jié)點的未遍歷neighbors放進這個隊列，重復此過程直至隊列為空妓盲。這種方式是層層遞進的聚至。DFS則是一條道先走到黑，然后再換一條路本橙，用遞歸實現(xiàn)會簡潔很多扳躬。兩個方法都需要一個輔助空間visited來記錄已經(jīng)遍歷過的節(jié)點，避免走回頭路。假如需要記錄路徑贷币，可以用path代替visited击胜。
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['D', 'E'], 'D': ['E'], 'E': ['A']}
# BFS DFS
def recursive_dfs(graph, start, path=[]):
path = path + [start]
for node in graph[start]:
if node not in path:
path = recursive_dfs(graph, node, path)
return path
def iterative_dfs(graph, start):
path = []
# dfs uses a stack, so that it visits the last node
# pushed to stack (explores as deep as possible first)
stack = [start]
while stack:
v = stack.pop() # pops out the last in (go deeper)
if v not in path:
path += [v] # add v to path
stack += graph[v] # push v's neighbors to stack
return path
def iterative_bfs(graph, start):
path = []
queue = [start]
# bfs uses a queue, so that it visits the nodes pushed
# to the queue first. So it first visits all the neighbors
# and then the neighbors' neighbors (explores the soroundings
# as much as possible without going deep)
while queue:
v = queue.pop(0) # pops out the first in (go wider)
if v not in path:
path += [v]
queue += graph[v] # push v's neighbors to queue
return path
兩種方法各有千秋。T:O(V+E) S:O(V)
** Dijkstra**
問題：在無向圖G=(V,E)中役纹，假設每條邊E[i]的長度為W[i]偶摔，找到頂點V0到其余各點的最短路徑。這個算法是典型的單源最短路徑算法促脉，要求不能出現(xiàn)負權值辰斋，即W[i]>=0.
算法的思想很簡單。在算法進行中的某個時刻瘸味，整個圖的所有頂點可以分成兩塊宫仗，一塊是已經(jīng)完成的，一塊是待完成的旁仿。那么待完成的肯定有一部分是和已經(jīng)完成的部分相連的藕夫，因此它們距離源點V0的路徑長度也是可以獲得的，從里面挑一個最小的加入已經(jīng)完成的部分枯冈，并更新這個點的下一層neighbors的可能路徑值毅贮。重復步驟直至所有點都完成。
事實上尘奏，因為剛開始只有W[i]的值滩褥，可以給每個點增加一個屬性，即到V0的最短路徑炫加。剛開始铸题，只有V0到自己的值是0，別的點都是正無窮琢感。然后考慮V0的neighbors，其可能（因為可能有更短的路徑）的路徑值就是V0的路徑值加上V0到其的W[i]探熔，選擇一個最小的驹针，確定其路徑值。然后再考慮V0和剛剛加進來的點的neighbors的可能路徑值诀艰，再找一個最小的柬甥。反復直至完成。
# Dijkstra T:O(V^2) S:O(V)
def popmin(pqueue):
# A (ascending or min) priority queue keeps element with
# lowest priority on top. So pop function pops out the element with
# lowest value. It can be implemented as sorted or unsorted array
# (dictionary in this case) or as a tree (lowest priority element is
# root of tree)
lowest = 1000
keylowest = None
for key in pqueue:
if pqueue[key] < lowest:
lowest = pqueue[key]
keylowest = key
del pqueue[keylowest]
return keylowest
def dijkstra(graph, start):
# Using priority queue to keep track of minium distance from start
# to a vertex.
pqueue = {} # vertex: distance to start
dist = {} # vertex: distance to start
pred = {} # vertex: previous (predecesor) vertex in shortest path
# initializing dictionaries
for v in graph:
dist[v] = 1000
pred[v] = -1
dist[start] = 0
for v in graph:
pqueue[v] = dist[v] # equivalent to push into queue
while pqueue:
u = popmin(pqueue) # for priority queues, pop will get the element with smallest value
for v in graph[u].keys(): # for each neighbor of u
w = graph[u][v] # distance u to v
newdist = dist[u] + w
if (newdist < dist[v]): # is new distance shorter than one in dist?
# found new shorter distance. save it
pqueue[v] = newdist
dist[v] = newdist
pred[v] = u
return dist, pred
可以看到其垄，這里對popmin的實現(xiàn)是用的比較原始的O（n）方法苛蒲，假如用堆的話，可以將效率提高為O(ElogV)绿满。
** Bellman-Ford**
上面提到臂外，Dijkstra不能在含有負權邊的圖上使用，而Bellman-Ford算法可以。但是這個算法效率更低漏健，為O（VE）嚎货。假如有負權回路，會報錯而不會繼續(xù)進行計算（負權回路的存在讓最短路徑變得沒有意義）蔫浆。
Bellman－Ford算法可以大致分為三個部分：
第一殖属，初始化所有點。每一個點保存一個值瓦盛，表示從原點到達這個點的距離洗显，將原點的值設為0，其它的點的值設為無窮大（表示不可達）原环。
第二挠唆，進行循環(huán)，循環(huán)下標為從1到n－1（n等于圖中點的個數(shù)）扮念。在循環(huán)內(nèi)部损搬，遍歷所有的邊，進行松弛計算巧勤。
第三弄匕，遍歷途中所有的邊（edge（u，v））剩瓶，判斷是否存在這樣情況：
d（v） > d (u) + w(u,v)
有則返回false城丧，表示途中存在從源點可達的權為負的回路亡哄。
為什么要循環(huán)n-1次？因為最短路徑最多n-1條邊（不會包含環(huán)）愿卸。
# Bellman-Ford T:O(VE) S:O(V)
# Step 1: For each node prepare the destination and predecessor
def initialize(graph, source):
d = {} # Stands for destination
p = {} # Stands for predecessor
for node in graph:
d[node] = float('Inf') # We start admiting that the rest of nodes are very very far
p[node] = None
d[source] = 0 # For the source we know how to reach
return d, p
def relax(node, neighbour, graph, d, p):
# Step 2: If the distance between the node and the neighbour is lower than the one I have now
if d[neighbour] > d[node] + graph[node][neighbour]:
# Record this lower distance
d[neighbour] = d[node] + graph[node][neighbour]
p[neighbour] = node
def bellman_ford(graph, source):
d, p = initialize(graph, source)
for i in range(len(graph) - 1): # Run this until is converges
for u in graph:
for v in graph[u]: # For each neighbour of u
relax(u, v, graph, d, p) # Lets relax it
# Step 3: check for negative-weight cycles
for u in graph:
for v in graph[u]:
assert d[v] <= d[u] + graph[u][v]
return d, p
Flord-Wayshall
該算法用于求圖中任意兩點的最短路徑，復雜度O（V^3）宦焦。這個算法是基于DP的一種算法。思想也非常簡單笼平，考慮節(jié)點u到節(jié)點v的距離為d[u][v]，假設有某個節(jié)點k使得u到k然后再到v的距離比原來的小寓调，那就替換之。
# Floyd-Warshall T:O(V^3) S:O(V)
def floydwarshall(graph):
# Initialize dist and pred:
# copy graph into dist, but add infinite where there is
# no edge, and 0 in the diagonal
dist = {}
pred = {}
for u in graph:
dist[u] = {}
pred[u] = {}
for v in graph:
dist[u][v] = 1000
pred[u][v] = -1
dist[u][u] = 0
for neighbor in graph[u]:
dist[u][neighbor] = graph[u][neighbor]
pred[u][neighbor] = u
for t in graph:
# given dist u to v, check if path u - t - v is shorter
for u in graph:
for v in graph:
newdist = dist[u][t] + dist[t][v]
if newdist < dist[u][v]:
dist[u][v] = newdist
pred[u][v] = pred[t][v] # route new path through t
return dist, pred