Blog·Tanky WooABOUTRSS

python实现深度优先搜索BFS

14 Apr 2012
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

首先给出待遍历的元组:

1 2 3

4 5 6

7 8 9

10 11 12

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

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

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

代码:

# -*- 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)

输出结果为:

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]]