[자료구조] 그래프 -2

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

그래프 탐색

• 그래프에서는 두 가지 방식으로 모든 정점을 방문
  
  1. 깊이 우선 탐색 (DFS : Depth First Search)
     
  2. 너비 우선 탐색 (BFS : Breadth First Search)
     
     

깊이 우선 탐색 (DFS : Depth First Search)

• 핵심 아이디어 : DFS는 실타래를 가지고 미로에서 출구를 찾는 것과 유사. 새로운 곳으로 갈 때는 실타래를 풀면서 진행하고, 길이 막혀 진행할 수 없을 때에는 실타래를 되감으며 왔던 길을 되돌아가 같은 방법으로 다른 경로를 탐색하여 출구를 찾는다
  
  

• 그래프에서의 DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고
  
• 방금 방문한 정점의 이웃 정점을 방문하며
  
• 이웃하는 정점들을 모두 방문한 경우에는 이전 정점으로 되돌아 가서 탐색을 수행하는 방식으로 진행
  
  

너비 우선 탐색 (BFS : Breadth First Search)

• 핵심 아이디어 : BFS는 연못에 돌을 던져서 만들어지는 동심원의 물결이 퍼져나가는 것 같이 정점들을 방문한다
  
  

• 임의의 정점 s에서 시작하여 s의 모든 이웃하는 정점들을 방문하고, 방문한 정점들의 이웃 정점들을 모두 방문하는 방식으로 그래프의 모든 정점을 방문
  
• 이진트리에서의 레벨순회와 유사
  
  

수행시간

• 각 정점을 한번씩 방문하며, 각 간선을 한번씩만 사용하여 탐색하기 때문에 O(N+M)의 수행시간이 소요
  
• BFS와 DFS는 정점의 방문순서나 간선을 사용하는 순서만 다를 뿐이다
  
  

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/-t8EjJTazRM