python实现深度优先搜索BFS

首先给出待遍历的元组:

1   2   3

4   5   6

7   8   9

10 11 12

 

然后用BFS遍历数组,方向随便定义为下,上,右,左。

定义一个二位列表vis保存点的状态(是否被遍历过)

每次访问一个点时,输出此点的坐标,以及vis列表。

 

代码:

[code language=”python”]
# -*- coding:utf-8 -*-
# Tanky Woo
# BFS

# direction– down, up, right, left
di = ((1, 0), (-1, 0), (0, 1), (0, -1))

# DFS function
def BFS(x, y):
global graph
global vis
xlen = 4
ylen = 3

if 0<=x<xlen and 0<=y<ylen:
if vis[x][y] == 1:
return
vis[x][y] = 1
print "visit: ", x, y
print vis
for i in range(4):
if 0<=x+di[i][0]<xlen and 0<=y+di[i][1]<ylen :
BFS(x+di[i][0], y+di[i][1])

if __name__ == ‘__main__’:
graph = ((1,2,3), (4,5,6), (7,8,9), (10,11,12))

vis = [[0]*3 for _ in range(4)]

BFS(0, 0)

[/code]

输出结果为:
[code language=”python”]
visit: 0 0
[[1, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
visit: 1 0
[[1, 0, 0], [1, 0, 0], [0, 0, 0], [0, 0, 0]]
visit: 2 0
[[1, 0, 0], [1, 0, 0], [1, 0, 0], [0, 0, 0]]
visit: 3 0
[[1, 0, 0], [1, 0, 0], [1, 0, 0], [1, 0, 0]]
visit: 3 1
[[1, 0, 0], [1, 0, 0], [1, 0, 0], [1, 1, 0]]
visit: 2 1
[[1, 0, 0], [1, 0, 0], [1, 1, 0], [1, 1, 0]]
visit: 1 1
[[1, 0, 0], [1, 1, 0], [1, 1, 0], [1, 1, 0]]
visit: 0 1
[[1, 1, 0], [1, 1, 0], [1, 1, 0], [1, 1, 0]]
visit: 0 2
[[1, 1, 1], [1, 1, 0], [1, 1, 0], [1, 1, 0]]
visit: 1 2
[[1, 1, 1], [1, 1, 1], [1, 1, 0], [1, 1, 0]]
visit: 2 2
[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 0]]
visit: 3 2
[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]]
[/code]

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《python实现深度优先搜索BFS》有298个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注