DFS, BFS

그래프 탐색(순회)하는 방법 으로 DFS, BFS 두 가지를 정리해보자. 

1. DFS 

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

- depth-frst-search

- 깊이 우선 탐색

- 모든 노드 탐색하고 싶을 때

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가

더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서

그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.

2. BFS

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
- breadth-frist-search

- 너비 우선 탐색

- 가까운 노드부터 찾을 때 

예를 들어, 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

 

3. 비교

- 시간 복잡도는 노드의개수(N), 간선의개수(E)일 때 O(N+E)DLEK. 

 

4. 구현

- BFS: stack을 이용한 재귀함수 

- DFS: queue을 이용한 재귀함수 

- 임의의 그래프에서 시작노드를 입력하면 각각 bfs, dfs를 통해 전체를 순회하는 경로를 출력하게 해보자.

visited = [False] * 9

def dfs(graph, x):
    visited[x] = True
    print(x, end = ' ')
    for y in graph[x]:
        if visited[y] == False:
            dfs(graph, y)


from collections import deque

def bfs(graph, x):
    visited = [False] * 9
    queue = deque([x])
    visited[x] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for y in graph[v]:
            if visited[y] == False:
                queue.append(y)
                visited[y] = True

 

 

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

 

Python｜탐색 알고리즘 뿌시기 (1) DFS, BFS 의 개념과 구현 :: Jeina, De'vLog (tistory.com)

출처: https://devuna.tistory.com/32 [튜나 개발일기]