[그래프] 너비우선탐색 BFS & 깊이우선탐색 DFS

• 모든 정점을 방문하는 방법 : 너비우선탐색 BFS, 깊이우선탐색 DFS
  
  • 너비우선탐색 BFS
    • 먼저 루트의 자식을 차례로 방문함
    • 다음으로 루트 자식의 자식, 루트에서 2개의 간선을 거쳐서 도달할 수 있는 정점 방문
    • 루트로부터 3개의 간선을 거쳐서 도다랗는 정점들
    • 4개, 5개... 순으로 방문함
  • 깊이우선탐색 DFS
    • 루트 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려감
    • 더 이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려감
• BFS는 옆으로 쭉 훑어 나가고, DFS는 아래로(깊이) 갈 수 있는 데까지 갔다가 막히면 되돌아와서 다시 내려감
• DFS에 기반한 탐색 방법을 백트래킹 이라고 부르기도 함

 

 

BFS

• 수행 순서
  • 시작 정점으로 정해진 정점을 방문(1로 표시)
  • 정점 1에 인접한 정점을 모두 방문(2, 3, 4로 표시)
  • 정점 2, 3, 4를 기준으로 인접한 또다른 정점이 있는지 방문.(5, 6, 7로 표시)
  • 반복하며 방문하지 않은 정점이 없어서 더 이상 갈 곳이 없으면 끝

 

 

DFS

• 수행 순서
  • 시작 정점으로 정해진 정점을 방문(1로 표시)
  • 정점1에 인접한 정점 중 하나를 방문(2로 표시)
  • 정점2에 인접하면서 방문하지 않은 총 3개의 정점 중 하나를 방문함(3으로 표시)
  • 정점3에 인접한 정점 중 방문하지 않은 2개의 정점 중 하나를 방문(4로 표시)
  • ...정점 5까지 반복. 5에 인접한 정점 중 방문하지 않은 정점이 없으면 따라서 왔던 길을 되돌아감
  • 되돌아가는 과정에서 방문여부를 확인. 방문하지 않은 정점이 있으면 방문한다.
  • 되돌아가며 시작 정점(정점1)로 도착하면 더 이상 갈 곳이 없으므로 끝낸다.

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」