[Algorithm] DFS/BFS 정리

그래프 탐색 알고리즘 : DFS/BFS

탐색(Search)란 많은 양의 데이터 중 원하는 데이터를 찾는 과정

대표적인 탐색 알고리즘

• DFS
• BFS

---

스택 Stack 📚

: 선입후출의 자료구조 - **입구와 출구가 동일한 형태**로 시각화 가능

큐 Queue 📑

: 선입선출의 자료구조 - **입구와 출구가 모두 뚫여 있는 터널과 같은 형탸**로 시각화 가능

---

DFS : Depth-First Search

: 깊이 우선 탐색 이라고 부르며 깊은 부분을 우선적으로 탐색하는 알고리즘

Stack 자료구조를 사용하며 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있으면 스택에 넣고 방문 처리,
   없다면 스택에서 최상단 노드를 꺼내기

3. 2번의 과정을 수행할 수 없을 때까지 반복

def DFS(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

print(DFS(graph_list, root_node))

BFS : Breadth-First Search

: 너비 우선 탐색 이라고 부르며 가까운 노드부터 우선적으로 탐색하는 알고리즘

Queue 자료구조를 사용하여 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 삽입하고 방문 처리

3. 2번의 과정을 수행할 수 없으 ㄹ때까지 반복

def BFS(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS(graph_list, root_node))