DFS / BFS

DFS(Depth-First Search) : 깊이 우선 탐색

 

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택 자료구조 혹은 재귀 함수를 이용한다.

출처 : https://ko.wikipedia.org/wiki/깊이_우선_탐색

✔︎ 동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 수행한다.

✔︎ 깊이 제한 : 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위함이다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다.

✔︎ 백트래킹  :  부모노드로 되돌아오는 과정을 말한다.

 

장단점 )

 

장점 

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. (따라서 깊이 제한 이용해야 한다.)
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 

 

코드 예제 )

출처 : https://www.youtube.com/watch?v=7C9RgOcvkvo

 

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 = [
    [], # 1부터 시작이기 때문에 이거 무시되게
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

➡︎ 1 2 7 6 8 3 4 5 

 

---

 

BFS(Breadth-First Search) :  너비 우선 탐색

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘. queue 자료구조를 이용한다.

출처 : https://wizdom.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F

 

✔︎ 동작 과정 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번 과정 수행할 수 없을 때까지 반복한다.

 

장단점 )

장점

• 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

코드 예제 )

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    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 = [
    [], # 1부터 시작이기 때문에 이거 무시되게
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현
visited = [False] * 9

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)

➡︎ 1 2 3 8 7 4 5 6 

 

 

---

참조

https://www.youtube.com/watch?v=7C9RgOcvkvo 

https://ko.wikipedia.org/wiki/너비_우선_탐색

https://ko.wikipedia.org/wiki/깊이_우선_탐색