DFS, BFS

• src : https://github.com/pine939/Programming/tree/master/practice/graph_search
• graph 예시

DFS (Depth-First Search)

• 탐색 시작 노드에서 해당 분기를 완벽하게 탐색하는 방법이다.
• 예를 들어, 미로 찾기에서 갈림길의 한 방향을 선택 후, 갈 수 있을 때 까지 가다가 더 이상 갈 수 없을 때 가장 최근의 갈림길의 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색이라고 할 수 있다.
• 스택과 재귀를 사용하여 탐색을 구현할 수 있다.

구현하기

• Point 1 : stack은 backtracking용으로 사용한다. 따라서, cur 노드를 먼저 stack에 넣는다.

• Point 2 : stack에 push될 때 해당 노드는 탐색되었음을 의미한다.

• Recursive 구현
  • 1 2 3 4 5 6 7 8 9 10
  • 소스 코드
• Stack을 사용한 구현
  • 소스 코드

BFS (Breadth-First Search)

• 탐색 시작 노드에서 인접한 노드들을 먼저 탐색하는 방법이다.
• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
• 큐를 사용하여 탐색을 구현할 수 있다.

구현하기

• Point : queue에서 pop할 때 해당 노드는 탐색되었음을 의미한다.

• Queue를 사용한 구현

  • 1 2 5 9 3 6 8 10 4 7
  • 소스 코드