그래프 탐색은 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다. 그 방법에는 깊이 우선 탐색과 너비 우선 탐색이 있다.
두 방법의 차이점을 개념과 아래의 그래프 예시(내가 임의로 만든 것)를 통해 살펴볼 것이다.
- 깊이 우선 탐색 (depth first search, DFS)
스택을 이용한 미로 탐색과 유사함.
-> 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향을 다시 탐색하는 방법으로 출구를 찾는다.
시작 정점 -> 인접 정점으로 깊이 탐색 진행
(방문한 정점은 방문되었다는 표시를 해야 하고, 탐색은 아직 방문하지 않은 정점으로만 가능함.
더 이상 방문하지 않은 정점이 없을 경우 마지막으로 방문한 정점으로 되돌아가서 인접 정점 탐색 재진행)
그래프의 진행은 아래와 같다. (읽는 순서는 왼 -> 오, 작은 값 우선)
탐색 순서: 1 2 6 7 3 4 5
c++ 코드로 BFS 알고리즘을 구현해보면 아래와 같다.
- 너비 우선 탐색 (breadth first search, BFS)
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법
큐 사용 -> 정점들이 방문될 때마다 큐에 인접 정점 삽입하고, 더 이상 방문할 인접 정점이 없을 경우 큐의 맨 앞에서 정점을 꺼내 그 정점과 인접한 정점들을 차례대로 방문한다.
그래프의 진행 방식은 아래와 같다.
탐색 순서: 1 2 3 5 6 4 7
c++ 코드로 DFS알고리즘을 구현해보면 아래와 같다.
<관련 문제풀이>
-BFS: BJ 5014
https://www.acmicpc.net/problem/5014
문제풀이:
참고: C++로 쉽게 풀어쓴 자료구조,
(문제풀이) https://baebalja.tistory.com/m/452
