탐색

1.DFS(깊이 우선 탐색)

• 그래프 완전 탐색 기법 중 하나
• 시작 노드에서 출발하여 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 탐색하는 알고리즘
• 재귀 함수로 구현
• 스택 자료구조 이용 (FIFO 먼저 들어온 데이터가 나중에 나간다.)
• 시간 복잡도 (노드 = V,에지수 : E ) : O(V+E)
• 스택 오버플로(A라는 함수에 A를 또 부르는 식으로 무한대로 부르는 것)에 유의 해야함

1) 깊이 우선 탐색의 핵심 이론

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.
• 그래프는 인접 리스트로 표현하겠다.
• 후입 선출의 특성을 가지고 있다.

2.BFS(너비 우선 탐색)