1. bfs dfs
  2. 概念
    1. 範例
    2. 例題

bfs dfs

最後更新: 作者: 字数: 562 预计阅读时间: 2min

bfs dfs

python

概念

bfs是用queue來存放鄰近的節點，並將每一層的節點走完再去走下一層這樣子去走訪，而dfs則是用stack來儲存，再從上面取出，也就是說他是走到底再返回。

範例

如果想要走訪0 1, 0 2, 1 2, 1 3, 2 3, 2 4, 3 4, 3 5的圖形的話我們可以用bfs或dfs，那麼我們這邊先示範一下，而如我們所說的會用到queue所以要import deque，還有另外dfs會用到遞迴:

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
from collections import deque


def graph():
    n = int(input())
    e = int(input())
    graph = [[] for i in range(n)]
    for i in range(e):
        k = list(map(int, input().split()))
        graph[k[0]].append(k[1])
        graph[k[1]].append(k[0])
    return graph


def bfs(graph, s):
    dq = deque([])
    dq.append(s)
    seen = set()
    seen.add(s)

    while len(dq) > 0:
        v = dq.popleft()
        for i in graph[v]:
            if i not in seen:
                dq.append(i)
                seen.add(i)
        print(v)


bfs(graph(), 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def graph():
    n = int(input())
    e = int(input())
    graph = [[] for i in range(n)]
    for i in range(e):
        k = list(map(int, input().split()))
        graph[k[0]].append(k[1])
        graph[k[1]].append(k[0])
    return graph


def dfs(graph, s):
    global seen
    seen.add(s)
    print(s)
    for i in graph[s]:
        if i not in seen:
            seen.add(i)
            dfs(graph, i)


seen = set()
dfs(graph(), 0)

上面的graph()是圖形的輸入

例題

題目
沒有意外的話我們用python寫應該會超時，但沒關係，我們可以試試用dfs來寫，讓他每一次遇到一個.，如果是沒有遇過的狀況下，就進行dfs搜尋:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import sys
sys.setrecursionlimit(10**6)
 
def inp():
    n, m = map(int, input().split())
    graph = []
    for i in range(n):
        graph.append(input())
 
    return graph
 
 
def dfs(graph, v):
    global seen
    seen.add(v)
    if (
        v[0] - 1 >= 0
        and graph[v[0] - 1][v[1]] == "."
        and (v[0] - 1, v[1]) not in seen
    ):
        dfs(graph, (v[0]-1, v[1]))
 
    if (
        v[0] + 1 < len(graph)
        and graph[v[0] + 1][v[1]] == "."
        and (v[0] + 1, v[1]) not in seen
    ):
        dfs(graph, (v[0]+1, v[1]))   
 
    if (
        v[1] + 1 < len(graph[0])
        and graph[v[0]][v[1] + 1] == "."
        and (v[0], v[1] + 1) not in seen
    ):
        dfs(graph, (v[0], v[1] + 1))
 
    if (
        v[1] - 1 >= 0
        and graph[v[0]][v[1] - 1] == "."
        and (v[0], v[1] - 1) not in seen
    ):
        dfs(graph, (v[0], v[1] - 1))
 
 
def main(graph):
    global rooms
    for i in range(len(graph)):
        for j in range(len(graph[0])):
            if graph[i][j] == "." and (i, j) not in seen:
                dfs(graph, (i, j))
                rooms+=1
 
seen = set()
rooms = 0
 
main(inp())
print(rooms)