[ Chapter.05 ] DFS / BFS 이론

그래프의 기본 구조

DFS / BFS 알고리즘에 대한 설명에 앞서, 그래프의 기본 구조 두 가지에 대해 살펴보겠습니다.

 

01) 인접 행렬

인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현하는 방식 입니다. 

연결 되어 있지 않은 노드끼리는 무한이라고 작성합니다 (INF)

 

모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 낭비됩니다.

 

 

02) 인접 리스트

인접 리스트는 각각의 노드에 연결된 노드의 정보를 차례대로 연결하여 저장합니다. 

 

연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용합니다. 

연결된 데이터를 하나씩 확인해야 하기 때문에 정보를 얻는 속도가 느립니다.

 

DFS

Depth-First Search 깊이 우선 탐색이라고 부릅니다.

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다. 

 

• 스택 자료구조를 이용합니다. 
• 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 간결하게 구현할 수 있습니다. 
• 데이터의 개수가 n인 경우, O(n)의 시간이 소요됩니다.

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 

 

def dfs(graph, v, visited):

  visited[v] = 1
  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]
]

visited = [0] * 9

dfs(graph, 1, visited)

 

 

 

 

 

BFS

Breadth First Search 너비 우선 탐색이라고 부릅니다. 

그래프에서 가까운 노드부터 탐색하는 알고리즘 입니다. 

 

• 큐 자료구조를 이용하는 것이 정석입니다.(선입선출)
• deque 라이브러리를 사용하는 것이 좋습니다.
• 탐색을 수행함에 있어 O(n)의 시간이 소요됩니다. 
• 일반적으로 실제 수행 시간은 DFS보다 좋습니다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 합니다.

 

from collections import deque

def bfs(graph, start, visited):

  q = deque([start])

  visited[start] = 1

  while q: # 큐가 빌 때까지 반복
    v = q.popleft()
    print(v, end = ' ')

    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = 1

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

visited = [0] * 9

bfs(graph, 1, visited)