그래프 탐색 알고리즘 DFS, BFS

그래프 탐색 알고리즘

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

 

활용되는 자료구조

스택 자료 구조

• 먼저 들어온 자료가 나중에 나가는(선입후출) 자료구조
• 입구와 출구가 동일한 형태

큐 자료구조

• 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 입구와 출구가 모두 뚫혀 있는 터널과 같은 형태

 

 

DFS (깊이 우선 탐색)

개념

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조를 이용하거나 재귀 함수로 구현

 

핵심 이론

• DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요

 

과정

1. 탐색 시작 노드를 스택에 삽입하고 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리.
   방문하지 않은 인접노드가 없다면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

BFS (너비 우선 탐색)

 

개념

• 그래프에서 시작 노드를 기준으로 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용

 

과정

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

 

 

 

출처

https://yoongrammer.tistory.com/45

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』 , 한빛미디어

김종관, 『 Do it! 알고리즘 코딩 테스트 자바』, 이지스퍼블리싱