Neaya~

笔记、记录、总结

python模拟bfs和dfs，只需修改一处

发表于 更新于 分类于 评论数：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

摘要：BFS，DFS

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
"""
# @Time    :  2020/11/8
# @Author  :  Jimou Chen
"""


# 广搜
def bfs(graph, start):
    queue = [start]  # 先把起点入队列
    visited = set()  # 访问国的点加入
    visited.add(start)

    while len(queue):
        vertex = queue.pop(0)
        # 找到队列首元素的连接点
        for v in graph[vertex]:
            if v not in visited:
                queue.append(v)
                visited.add(v)
        # 打印弹出队列的该头元素
        print(vertex, end=' ')


if __name__ == '__main__':
    graph = {
        'A': ['B', 'D', 'I'],
        'B': ['A', 'F'],
        'C': ['D', 'E', 'I'],
        'D': ['A', 'C', 'F'],
        'E': ['C', 'H'],
        'F': ['B', 'H'],
        'G': ['C', 'H'],
        'H': ['E', 'F', 'G'],
        'I': ['A', 'C']
    }

    bfs(graph, 'A')

1
2
A B D I F C H E G 
Process finished with exit code 0

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
# @Time    :  2020/11/8
# @Author  :  Jimou Chen
"""


# 深搜
def dfs(graph, start):
    stack = [start]
    visited = set()
    visited.add(start)

    while len(stack):
        vertex = stack.pop()  # 找到栈顶元素
        for v in graph[vertex]:
            if v not in visited:
                stack.append(v)
                visited.add(v)

        print(vertex, end=' ')


if __name__ == '__main__':
    graph = {
        'A': ['B', 'D', 'I'],
        'B': ['A', 'F'],
        'C': ['D', 'E', 'I'],
        'D': ['A', 'C', 'F'],
        'E': ['C', 'H'],
        'F': ['B', 'H'],
        'G': ['C', 'H'],
        'H': ['E', 'F', 'G'],
        'I': ['A', 'C']
    }

    dfs(graph, 'E')

1
2
E H G F B A I D C 
Process finished with exit code 0

总结

  • 很明显一个用了队列，一个用了栈
  • 利用python语言优势，只需改动pop即可
Welcome to reward