DFS(깊이 우선 탐색) VS BFS(너비 우선 탐색)

그래프란?

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말한다.

그래프의 탐색이란?

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

DFS (깊이 우선 탐색)

• 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 (그러니까 가장 끝까지 전부 탐색하고 또 다른 탐색을 한다는 뜻임)
• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
• DFS가 BFS보다 좀 더 간단함
• 검색 속도 자체는 BFS에 비해서 느림
• 스택 또는 재귀함수로 구현
• 경로들의 특징을 각각 저장해둬야 할 때, 검색 대상 그래프가 정말 클 때 사용하면 좋음

def dfs(graph, start):
    visited = [] # 방문한 노드를 저장할 리스트
    stack = [start] # 시작 노드를 스택에 저장
    while stack:
        node = stack.pop() # 스택에서 노드를 꺼냄
        if node not in visited:
            visited.append(node) # 방문한 노드를 저장
            stack.extend(graph[node] - set(visited)) # 방문하지 않은 인접 노드를 스택에 추가
    return visited

BFS (너비 우선 탐색)

• 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식.
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 사용
• 큐를 사용하여 구현
• 최단 거리를 구해야 할 때, 검색 대상의 규모가 크지 않고 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않을 때 사용하면 좋음

from collections import deque

def bfs(graph, start):
    visited = [] # 방문한 노드를 저장할 리스트
    queue = deque([start]) # 시작 노드를 큐에 저장
    while queue:
        node = queue.popleft() # 큐에서 노드를 꺼냄
        if node not in visited:
            visited.append(node) # 방문한 노드를 저장
            queue.extend(graph[node] - set(visited)) # 방문하지 않은 인접 노드를 큐에 추가
    return visited

참고

https://devuna.tistory.com/32
https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
https://velog.io/@gusdh2/DFS-vs-BFS-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89-vs-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89