[알고리즘] BFS(너비우선탐색)과 DFS(깊이우선탐색)

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

• 현재 정점에서 연결된 가까운 점들부터 탐색하는 방법
• 큐(Queue) 자료구조 이용

def bfs(graph, start_node):
    visit = list()
    queue = [start_node]
    
    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
    return visit

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'G', 'H', 'I'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
    'G': ['C'],
    'H': ['C'],
    'I': ['C', 'J'],
    'J': ['I']
}

print(bfs(graph, 'A'))

<output>
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

pop(0) 은 시간복잡도가 O(N) 이라 매우 비효율적인 코드가 만들어 진다. 따라서 collections 라이브러리의 deque를 사용한다.

from collections import deque

def bfs(graph, start_node):
    visit = list()
    queue = list()
	
    queue = deque(start_node)	# append
    
    while queue:
        node = queue.popleft()	# pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
    return visit

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'G', 'H', 'I'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
    'G': ['C'],
    'H': ['C'],
    'I': ['C', 'J'],
    'J': ['I']
}

print(bfs(graph, 'A'))

<output>
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

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

• 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색하는 방법
• 스택(Stack) 자료구조 이용

def dfs(graph, start_node):
    visit = list()
    stack = [start_node]
    
    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])
    return visit

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'G', 'H', 'I'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
    'G': ['C'],
    'H': ['C'],
    'I': ['C', 'J'],
    'J': ['I']
}

print(dfs(graph, 'A'))

<output>
['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']

참고 사이트

https://www.fun-coding.org/Chapter18-dfs-live.html