그래프 탐색

그래프 탐색이요?…

간단합니다. 하나의 정점에서 시작하여 차례대로 모든 정점들을 한 번씩 방문하는것이죠!

그렇다면 방문하는 기준이 다른 여러가지 방식들이 존재하겠죠?

오늘은 깊이 우선 탐색! 이라는것에 대해 알아보도록 하겠습니다!

• 깊이 우선 탐색 DFS(Depth-First Search)

---

DFS (Depth-First Search)

말 그대로 루트 노드(혹은 다른 임의의 노드)에서 시작하여 다음 분기로 가기전에 해당 분기를 끝까지 탐색하는 방법

• 넓게~ 탐색하는게 아닌 (근처에 노드들을 다 방문해가는게 아닌) 깊게!!!(한가지 분기점의 끝까지) 탐색하는것입니다.
• 완전탐색을 하고자할때 DFS탐색방식을 이용합니다.
• 미로를 예로들어보면 한방향으로 일단 끝까지 갔다가 막혀있으면 다시 되돌아가 처음 만나는 분기점에서 다시 끝까지
• 가보는것입니다.

특징:

• 자기 자신을 호출하는 순환 알고리즘의 형태입니다. (재귀호출)
• 트리 자료구조의 모든 순회 방식은 DFS방식의 한 종류 입니다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것입니다.