DFS(Depth-First Search), BFS(Beneath-First Search)

대표적인 크래프 탐색 알고리즘이다.

• 탐색(search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘

DFS(Depth-First-Search)

깊이 우선 탐색, 깊은 부분을 우선적으로 탐색하는 방법
스택 자료구조(혹은 재귀)를 이용하며 구체적인 동작 과정은 다음과 같다.

Stack

먼저 들어 온 데이터가 나중에 나가는 선입후출의 자료구조
입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.(박스쌓기)
단순하게 파이썬에서는 리스트, append와 pop를 사용하면 된다.

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

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

BFS(Breadth-First Search)

BFS는 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조를 이용한다.
먼저 들어온 데이터가 먼저 나가는 선입선출의 자료구조
입구와 출구가 모두 뚫려 있는 터널과 같은 형태(은행)

from collections import deque
# 큐 구현을 위해 deque 라이브러리를 사용한다.
queue=deque()
queue.append(6)
queue.popleft()
print(queue)

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

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

DFS와 BFS는 알고리즘 기본이고 자주 나오기 때문에,
많은 연습을 통해 숙지해두자.