用adjacency list實(shí)現(xiàn)的BFS槽畔。
用2個(gè)list儲(chǔ)存狀態(tài)：先初始化color洪灯，把所有點(diǎn)設(shè)為0，即還沒(méi)遍歷竟痰。然后把遍歷過(guò)的點(diǎn)標(biāo)成1；第二個(gè)List掏呼，Q坏快，作用是deque（先進(jìn)先出），把正在遍歷的點(diǎn)憎夷，比如點(diǎn)1莽鸿，push進(jìn)deque，然后把與1相鄰的點(diǎn)再push進(jìn)deque。然后再把1從deque祥得，即Q中刪除兔沃。
def graph_BFS(G,s):
inf = 1e8
color = []
Q = []
count = 0
n = len(G)
for v in range(0,n):
color.append(0)
Q.append(s)
count = count + 1
color[s] = 1
while(Q!=[]):
temp = Q[0]
print temp
#下面是把color不為1的graph[count - 1]里的item放進(jìn)Q
if(count-1<n):
for i in G[count-1]:
if(color[i] == 0):
Q.append(i)
Q.remove(temp)
count = count + 1
#放進(jìn)Q里的item變顏色
for v in Q:
color[v] = 1
graph = [[1,2,3],[5],[],[4],[5],[]]
graph1 = [[1],[2,3,4],[3,4],[],[]]
graph2 = [[1,2],[3],[0,4,5],[],[2,5,7],[2,4,7,6],[5,7],[4,5,6]]
source = 0
graph_BFS(graph2,source)
[github代碼地址]https://github.com/will-I-amor/python/blob/master/BFS.py
