DFS/BFS

대표적인 그래프 탐색 알고리즘

 

---

 

DFS

Depth-First Search 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며, 스택 자료구조나 재귀 함수를 이용한다.

• 탐색 시작 노드로 재귀함수를 호출해 방문 처리한다.
• 현재 방문 노드에서 방문하지 않은 인접 노드가 하나라도 있으면 그 노드로 재귀함수를 호출해 방문 처리한다.
• 방문하지 않은 인접 노드가 없으면 해당 재귀 함수는 종료된다.
• 더 이상 2 - 3번의 과정을 수행할 수 없을 때까지 반복한다.

# 재귀함수로 구현한 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)

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

 

---

 

BFS

Breadth-First Search 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이며, 큐 자료구조를 이용한다.

• 탐색 시작 노드를 큐에 삽입하고 방문 처리
• 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
• 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

from collections import deque

def bfs(graph, start, visited):
  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
  
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)