📌 다대다 비선형 자료구조(그래프, 트리)에서 완전 탐색 했을 때 우선순위 기준은 아래 두 종류가 있다
- 너비우선
- 깊이우선
1. 미리 정의
- 높이 : 루트에서 자신까지 오는 데에 사용되는 간선 수
- A-B : A의 자식이 B 노드다!
- 간접적으로 A-B, A-C를 통해 A->C의 간접 관계를 알 수 있다. (사실은 B로 가야 연결 관계 알 수 있긴 함)
2. 너비 우선 순위란
- 루트(높이가 0)부터 높이가 높은 순서까지 노드를 탐색하는 방식
- 자식 간선 우선 : 부모는 딱 자기 자식 노드까지만 탐색한다. 그 아래 자식의 자식 노드는 참견 안 함
- B에 갔을 때 새롭게 알게 된 관계들을 기억해둬야함 && 들어간 순서대로 출력해야함 -> 큐를 이용한다.
인접한 노드들에 대해 탐색한 후, 차례로 다시 너비우선 탐색
- 루트부터 연결된 노드만!! 큐잉(방문ㄴㄴ 큐잉 ㅇㅇ)
- 큐잉한 순서대로 방문
- 방문할 때마다 자식 큐잉
3. 큐를 스택으로 바꿔보면 바로 DFS 탐색 결과로 나옴
- 깊이를 따라가는 탐색 : 한 놈만 잡어~~
- 스택을 사용하는 것이아니라, 재귀 호출을 사용하면 스택을 사용한 느낌이 남!
- 재귀 장점 : 호출 프레임이 쌓일 때 쓰고 있었던 지역변수를 매개변수로 건냄. 각각의 메소드 프레임은 자신만의 고유한 메소드 프레임을 쓴다. -> 서로의 지역변수를 쓰기 때문에 상태가 그대로 남아있다.
- 재귀 호출하는 순간 스냅샷처럼 상태가 보존됨. 상태 관리를 직접 하지 않아도 되기 때문에, 코드가 훨씬 간단해짐. 만약 직접 스택을 이용해서 구현한다면 이러한 상태들을 모두 직접 관리해야 해서 어렵고 번거로울 것.
- 왜 재귀냐 : "플랫하게" 자기 자식만 챙기자~~. + 자식 노드 탐색하는 방식은 같음. 나는 내가 할 일만 하고 나머지넘겨 ->재귀