특징 - 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있음 - 전위 순회(Pre-Order-Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류 - 어떤 노드를 방문했었는지 여부를 반드시 검사해야함 ▶ 검사하지 않으면 무한루프에 빠질 위험이 있음 - Stach 자료구조(후입선출)사용
과정
a노드(시작 노드)방문 ▶ 방문한 노드는 방문했다고 표시
a와 인접한 노드를 차례로 순회함 ▶ a와 인접한 노드가 없다면 종료
a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문 ▶ b를 시작 정접으로 DFS를 다시 시작하여 b의 이웃 노드를 방문
b의 분기를 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾음 ▶ b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문 할 수 있다는 뜻 ▶ 아직 방문 안된 정점이 없으면 종료 ▶있으면 다시 그 정점을 시작정점으로 DFS를 시작
3. BFS(Breadth-First Search) : 너비 우선 탐색
그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
특징 - 직관적이지 않음 ▶ BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있음 - 재귀적으로 동작하지 않음 ▶어떤 노드를 방문 했었는지 여부를 반드시 검사해야함 ▶검사하지 않으면 무한루프에 빠질 가능성있음 - Queue(선입선출) 사용 - 'Prim', 'Dijkstra'알고리즘과 유사
a노드(시작노드)방문 (방문한 노드 체크) - 큐에 방문된 노드를 삽입 - 초기 상태의 시작 노드만 저장 ▶ a노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문
큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문 - 큐에서 꺼낸 노드 방문 - 큐에서 꺼낸 노드와 인접한 노드 방문 ▶ 인접한 노드가 없다면 큐의 앞에서 노드를 꺼냄 - 큐에 방문된 노드를 삽입
