[알고리즘 개념] DFS, BFS (Depth-First Search, Breadth-First Search)

DFS (Depth-First Search)

개념

• 깊이 우선 탐색으로 그래프에서 깊이가 깊은 부분을 우선적으로 탐색하는 알고리즘

• 스택 혹은 재귀를 이용한다

  • 동작
    1. 현재 노드를 방문처리 한다
    2. 현재 노드와 연결된 모든 노드 중 방문하지 않은 노드를 방문한다
    3. 모든 노드를 방문할 때 까지 반복한다

• 그래프 혹은 트리에서 모든 노드를 탐색하는 데 사용한다

• 순환 알고리즘(자기 자신을 호출)이므로 노드 방문 여부 리스트가 필요하다

DFS 파이썬 구현

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9

dfs(graph, 1, visited)

DFS : 1 2 7 6 8 3 4 5

BFS (Breadth-First Search)

개념

• 너비 우선 탐색으로 그래프에서 가까운 노드를 우선적으로 탐색하는 알고리즘

• 큐를 이용한다

  • 동작
    1. 현재 노드를 큐에 삽입하고 방문처리 한다
    2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 한다
    3. 모든 노드를 방문할 때 까지 반복한다

• 그래프 혹은 트리에서 모든 노드를 탐색하는 데 사용한다

• 순환 알고리즘(자기 자신을 호출)이므로 노드 방문 여부 리스트가 필요하다

DFS 파이썬 구현

from collections import deque


def bfs(graph, start, visited):

    queue = deque([start])

    visited[start] = True

    while queue :

        v = queue.popleft()
        print(v, end=' ')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True



graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9

bfs(graph, 1, visited)

BFS : 1 2 3 8 7 4 5 6

[출처 : 나무위키]
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3