DFS, BFS

1. DFS(Depth First Search)

- 스택 또는 재귀를 사용해서 구현

위의 트리를 인접행렬로 나타내는 코드

adj = [[0] * 13 for i in range(13)]
adj[0][1] = adj[0][7] = 1
adj[1][2] = adj[1][5] = 1
adj[2][3] = adj[2][4] = 1
adj[5][6] = 1
adj[7][8] = adj[7][9] = 1
adj[9][10] = adj[9][11] = adj[9][12] = 1

for row in adj:
    print(row)

13*13 행렬을 만들었다.

이를 토대로 dfs를 짜면

def dfs(now):
    for nxt in range(13):
        if adj[now][nxt]:
            print(now, '->', nxt, ' 1')
            dfs(nxt)

dfs(0)

이런식으로 만들 수 있고 결과를 보면

가장 바닥 노드까지 찍고 다시 옆으로 넘어가는 것을 확인할 수 있다.

 

2. BFS(Breadth First Search) 너비 우선 탐색

큐를 이용하여 구현한다.

같은 층위에 있는 노드를 쭉 탐색하고 다음 깊이로 넘어가는 방식.

위의 트리를 큐로 만들어서 BFS한다면

1. 큐에 0을 넣는다

2. 0을 꺼내고 0에서 갈 수 있는 1,2를 넣는다.

3. 1을 꺼내고 1에서 갈 수 있는 3,4를 넣는다.

4. 2를 꺼내고 2에서 갈 수 있는 5,6을 넣는다.

.........

이런식으로 모든 노드를 탐색할 수 있다.

코드로 나타내면 이렇다.

from collections import deque

adj = [[0] * 13 for i in range(13)]
adj[0][1] = adj[0][2] = 1
adj[1][3] = adj[1][4] = 1
adj[3][7] = adj[3][8] = 1
adj[4][9] = 1
adj[2][5] = adj[2][6] = 1
adj[6][10] = adj[6][11] = adj[6][12] = 1

def bfs():
    dq = deque()
    dq.append(0)
    while dq:
        now = dq.popleft()
        for nxt in range(13):
            if adj[now][nxt]:
                dq.append(nxt)
                print(now, '->', nxt)
bfs()

결과는