Table of Contents
图
以下面有向图为例, 以字典来表示这个图, 如下:
a, b, c, d, e, f = '1', '2', '3', '4', '5', '6'
g = {a: [b, d], b:[c, d], c:[], d:[e], e:[b, f], f:[c]}
算法
Go and check leetcode problem num 102
BFS用队列实现, DFS用栈实现. 由于栈和递归特殊的关系, DFS也可以用递归实现, 当然一般用递归实现.
BFS 通俗讲为从初始顶点开始, 先访问所有距离为1的顶点, 然后再访问所有距离为2的顶点(先被访问顶点的临节点要比后被访问节点临节点先访问)….
结果为: 1, 2, 4, 3, 5, 6
DFS 通俗讲为从初始顶点开始, 把一个分支访问完之后再访问下个分支…
结果为: 1, 2, 3, 4, 5, 6
实现
BFS
用queue实现
def BFS(g, begin_point):
visted = []
queue = [begin_point]
while len(queue) !=0:
pop = queue.pop(0)
if pop in visted:
continue
else:
visted.append(pop)
for next_point in g[pop]:
if next_point not in visted:
queue.append(next_point)
print(visted)
BFS(g, a)
['1', '2', '4', '3', '5', '6']
DFS
用栈实现
def DFS(g, begin_point):
visted = []
stack = [begin_point]
while len(stack) != 0:
pop = stack.pop()
if pop in visted:
continue
else:
visted.append(pop)
# lst = g[pop]
# print('lst', lst)
# print(type(lst))
# print('lst reverse', lst.reverse())
# r = lst.reverse()
for next_point in list(reversed(g[pop])):
if next_point not in visted:
stack.append(next_point)
# print('stack', stack)
# print('visted', visted)
print(visted)
DFS(g, a)
['1', '2', '3', '4', '5', '6']
用递归实现
visited = []
def DFS_r(g, begin_point):
visited.append(begin_point)
if len(visited) == len(g):
return
for next_point in g[begin_point]:
if next_point not in visited:
DFS_r(g, next_point)
DFS_r(g, a)
visited
['1', '2', '3', '4', '5', '6']
