[알고리즘] 그래프탐색: DFS

그래프 탐색이란

• 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법
• Graph: Vertex(어떤 것) + Edge(이어지는 것)
• 그래프 탐색 종류
  • BFS: Breadth-first search (너비 우선 탐색)
    • 자기 자식들을 먼저 탐색
  • DFS: Depth-first search (깊이 우선 탐색)
    • 자식의 자식을 먼저 탐색

Depth-first search (DFS, 깊이 우선 탐색)

---

• 1에서 부터 시작한다고 생각하면, 자식들 중 먼저 2의 자식을 탐색함
  • 1 -> 2
• 2가 먼저 들어왔으므로, 2의 자식을 먼저 탐색
  • 2 -> 4 (여기서 3은 1에서 탐색 됐으니 pass)
• 그 다음 4의 자식을 탐색
  • 4 -> 5
• 그 다음 5의 자식을 탐색
  • 5 -> 6 (여기서 3은 1에서 탐색 됐으니 pass)
• 그 다음 6의 자식은 없으므로 다시 1로 돌아가고, 1의 자식인 3을 탐색
• 최종적으로 탐색의 순서는 1 - 2 - 4 - 5 - 6 - 3

자료구조

• DFS에 알맞는 자료구조는 Stack임
• Stack는 후입선출의 형태를 띄우고 있는 자료구조임 (아래 그림)

• 그림에서 보면 2 - 4 - 5 순으로 들어옴
• 나갈 땐 앞에가 막혀서 5 - 4 - 2 순으로 나가게 됨

재귀함수

• DFS는 Stack을 자료구조로 사용하지만 재귀함수를 더 많이 사용하기도 함. 이유는 백트래킹 때문
• 그리고 왠만한 그래프 탐색은 사실 BFS로도 충분하다고 함
• 재귀함수는 자기 자신을 다시 호출하는 함수임.
• 주의할 점
  • 재귀함수가 종료되는 시점을 반드시 명시 하여야 함
  • 재귀함수의 깊이가 너무 깊어지면 메모리 터짐(Stack Overflow)

아이디어

• 우선 시작점에 연결된 vertex부터 찾기
• 연결된 vertex를 계속해서 찾기 (끝날 때 까지 꼬리를 끝까지 물어)
• 더이상 연결된 vertex가 없는 경우 다음으로 넘어가기

시간복잡도

• BFS와 마찬가지임
• DFS: O(V+E) (V: vertex의 수, E: edge의 수)

정리

• 검색할 그래프: 2차원 배열
• 방문여부 : 2차원 배열
• Queue 사용 안하고 재귀로 가기

참고자료

---

• 개발자 장고님의 유튜브 - BFS