[자료구조] BFS, DFS 총정리

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

:  시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문한다.

BFS, Wikimedia Commons

=> 큐(Queue) 자료구조를 사용해서 풀이한다.(deque이용 .appendleft()/popleft())

 

 

1)  노드를 방문하면서 인접한 노드 중 방문 하지 않았던 노드를 큐에 넣고(.append()),

2)  이전에 큐에 들어있던 노드를 popleft() 하여 뽑아내고 방문 리스트에 저장하면서 내려간다.(First In First Out)

 *deque 에서 popleft()를 사용해야한다

2021.06.19 - [python] - [자료구조] 파이썬 큐(Queue), deque 사용법 총정리

[자료구조] 파이썬 큐(Queue), deque 사용법 총정리

 

예시)

  * 위 그래프를 BFS 너비 우선 탐색하면 다음과 같다.

from collections import deque

graph_list = {1: set([2, 3]),
              2: set([4]),
              3: set([1]),
              4: set([2, 5, 6]),
              5: set([4, 6]),
              6: set([4])}
root_node = 1  # 시작 노드

def BFS_with_adj_list(graph, root):
    visited = []  # 방문 리스트
    queue = deque([root])  # 큐 = deque[root]

    while queue:
        n = queue.popleft()  # queue 의 맨 왼쪽 요소를 뽑아서 n 에 저장
        if n not in visited:  # n이 방문 리스트에 없으면
            visited.append(n)  # 방문한 곳에 n 추가
            queue += graph[n] - set(visited)  # 방문한 곳을 gragh 에서 제거하고 queue에 저장
            
        # 만약 n 이 방문 리스트에 있으면 위로 가서 다시 n = queue.popleft()
    return visited  # 방문 목록 리턴

print(BFS_with_adj_list(graph_list, root_node))

 

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

:  한 방향으로 끝까지 탐색한 뒤 직전 갈림길에서 방문하지 않았던 갈래로 내렸다가 올라오기를 반복하며 탐색한다.

DFS, Wikimedia Commons

=> 스택(stack) 을 사용해서 풀이한다. (.append()/pop())

1)  노드를 방문하면서 인접한 노드 중 방문 하지 않았던 노드를 큐에 넣고(.append()),

2)  이전에 스택에 들어있던 노드를 pop() 하여 뽑아내고 방문 리스트에 저장하면서 내려간다.(Lirst In First Out)

 

def DFS_with_adj_list(graph, root):
    visited = [] # 방문 리스트
    stack = [root] # 방문 해야 하는 노드리스트

    while stack:
        n = stack.pop() # stack 의 맨 오른쪽 요소를 뽑아서 n 에 저장

        if n not in visited: # n 이 방문 리스트에 없으면
            visited.append(n) # 방문한 곳에 n 추가
            stack += graph[n] - set(visited) # 방문한 곳을 graph 에서 제거하고 stack 에 저장

        # 만약 n 이 방문 리스트에 있으면 위로 가서 다시 n = queue.pop() 
    return visited
    
print(DFS_with_adj_list(graph_list, root_node))