[Python] DFS(깊이우선탐색)과 BFS(너비우선탐색)

1. DFS란

그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘이며 재귀함수로 구현할 수 있다. 1번에서 탐색을 시작하면 아래와 같이 동작하면서 노드를 방문한다. 방문한 노드를 순서로 출력하면 "1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12" 로 출력될 것이다.

 

1 → 2 → 3 → 4

   → 2 → 3 → 5

   → 2 → 6

   → 7

   → 8 → 9 → 10

   → 8 → 9 → 11

   → 8 → 12

 

2. DFS 구현해보기

# 실행결과 = 1→2→3→4→5→6→7→8→9→10→11→12→
visited = [False] * 12
def dfs(graph, v):
    if visited[v]:
        return
    
    # 방문노드 출력
    visited[v] = True
    print(v+1, end="→")

    # 해당노드에 연결된 노드취득
    links = graph[v]

    # 연결된 노드가 방문처리되지 않았다면 방문시도
    for link in links:
        if visited[link]:
            continue
        dfs(graph, link)

graph = [
    [1, 6, 7],
    [2, 5],
    [3, 4],
    [],
    [],
    [],
    [],
    [8, 11],
    [9, 10],
    [],
    [],
    []
]
dfs(graph, 0)

 

3. BFS란

그래프에서 인접한 노드를 우선으로 방문하는 알고리즘이며 큐를 통해 구현할 수 있다. 1번에서 탐색을 시작하면 아래와 같이 동작하면서 노드를 방문한다. 방문한 노드를 순서대로 출력하면 "1 → 2 → 7 → 8 → 3 → 6 → 9 → 12 → 4 → 5 → 10 → 11" 순서로 출력될 것이다.

 

1 → 2

1 → 7

1 → 8

 

1 → 2 → 3

1 → 2 → 6

1 → 8 → 9

1 → 8 → 12

 

1 → 2 → 3 → 4

1 → 2 → 3 → 5

1 → 8 → 9 → 10

1 → 8 → 9 → 11

 

4. BFS 구현해보기

# 출력결과 = 1 → 2 → 7 → 8 → 3 → 6 → 9 → 12 → 4 → 5 → 10 → 11 →
from collections import deque
visited = [False] * 12
def bfs(graph, v):
    if visited[v]:
        return
    
    q = deque()
    q.append(v)
    while q:
        p = q.popleft()
        
        if visited[p]:
            continue
        
        # 방문노드 출력
        print(p+1, end=" → ")
        visited[p]=True
        
        # 연결된 노드가 방문처리되지 않았다면 방문시도
        links = graph[p]
        for link in links:
            if visited[link]:
                continue
            q.append(link)

graph = [
    [1, 6, 7],
    [2, 5],
    [3, 4],
    [],
    [],
    [],
    [],
    [8, 11],
    [9, 10],
    [],
    [],
    []
]
bfs(graph, 0)