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

• 탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• DFS/BFS는 대표적인 그래프 탐색 알고리즘

스택(stack) 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
• 입구와 출구과 동일한 형태로 스택을 시각화할 수 있음

# 스택 구현 예제 (python)

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력

큐(queue) 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 입구와 출구과 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있음

# 큐 구현 예제 (python)

# 큐 (Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

DFS (Depth-First Search)

• 깊이 우선 탐색
• 스택 자료구조(혹은 재귀 함수)를 이용
  • 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  • 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리 / 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼냄
  • 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

# DFS 소스코드 예제 (python)

# DFS 메서드 정의
def dfs(grafh, 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)

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

# BFS 소스코드 예제 (python)

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visitied[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

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