1. 그래프 순회 방법 (Graph Traversal)
ㅇ 그래프 상에서,
- 모든 정점을 한번씩 만 방문하거나,
- 모든 정점을 한번씩 만 방문하면서 목표 정점을 찾아가거나,
- 또한, 특정 정점에서 다른 정점으로 갈수 있는지, 서로 연결되었는지 등을
- 확인하는 방법 ☞ 그래프 알고리즘 참조
ㅇ (명칭)
- 때론, 그래프 탐색 / 그래프 검색 (Graph Search) 방법 이라고 함
ㅇ (용도)
- 특정 정점에서 다른 정점으로 갈수 있는지, (연결성 검사, 경로 존재 검사)
- 서로 연결되었는지, (인접성 검사)
- 내부에 순환을 포함하는지 등을 확인하거나, (루프 검사)
- 미로 퍼즐 (미로 찾기, 출구 찾기) 등
* 다양한 그래프 알고리즘의 기초가 됨
ㅇ (요건)
- 어떤 식으로든 정점들이 순서화되어 있어야 함
- 방문했던 곳을 유지해야 함
- 아직 방문하지 않은 곳들에 대한 체계적인 다음 방문 방법이 제시되어야 함
ㅇ (참고)
- 다른 알고리즘과 마찬가지로, 알고리즘 그 자체 뿐 만아니라,
- 그래프 표현 방식(즉,자료구조)에 따라서 구현 용이성,성능 등이 영향 받음
2. 그래프 탐색의 대표적인 방식 둘(2)
ㅇ 깊이 우선 탐색 방법 (Depth First Search, DFS)
- 방법 요약 : 특정 정점에서 먼저 자식을 방문 후 더이상 자식이 없으면 전 단계 형제를 방문
- 유용한 자료구조 : 스택 이용
- 다음 미방문 노드 선택 기준
. 더 깊게
. 현재 노드
ㅇ 너비 우선 탐색 방법 (Breadth First Serach, BFS)
- 방법 요약 : 특정 정점에서 모든 형제를 방문 후에야 자식을 방문
- 유용한 자료구조 : 큐 이용
- 다음 미방문 노드 선택 기준
. 더 넓게
. 이전 노드