전공/그 외
[알고리즘] 전공 필기 시험 준비2
육지_거북이
2022. 4. 1. 20:32
그래프·트리 순회
깊이 우선 탐색(DFT, Depth First Search) :전위 순회(Pre-order traversal), 정위 순회(In-order traversal), 후위 순회(Post-order traversal)
너비 우선 탐색(Breadth First Search) : 레벨 순회
1. 깊이 우선 탐색(DFT, Depth First Search)
- 진행 가능한 노드가 없을 때까지 깊게 파고들며 탐색하는 방식
- 더이상 방문 가능한 노드가 없다면 이전의 위치로 돌아와 다른 방향으로 깊게 파고들며 탐색한다.
- 과거 위치의 인접 노드보다 현재 위치의 인접 노드를 먼저 방문한다는 특징을 가지므로, LIFO방식의 스택(stack)을 사용해 구현할 수 있다.
1) 전위 순회 (Pre-order traversal) : root → Left → Right
2) In-order traversal(중위,정위 순회) : Left → root → Right
3) Post-order traversal(후위 순회) : Left → Right → root
#전위 순회
def preorder(root):
if root != 0:
yield root.value
preorder(root.left)
preorder(root.right)
#중위 순회
def inorder(root):
if root != 0:
inorder(root.left)
yield root.value
inorder(root.right)
#후위 순회
def postorder(root):
if root != 0:
postorder(root.left)
postorder(root.right)
yield root.value2. 너비 우선 탐색(BFS, Breadth First Search)
- 깊이가 1인 노드들을 먼저 방문하고 나서, 그 다음에는 깊이가 2인 노드들, 깊이가 3인 노드들을 차례로 방문하다가 더이상 방문할 곳이 없으면 탐색을 마친다.
- 너비 우선 탐색은 그래프·트리 내 모든 노드를 방문하고 싶을 때, 찾는 것을 발견할 때까지 모든 노드를 적어도 한 번은 방문하고 싶을 때 사용하면 좋다.
- 방문한 노드를 저장하는 데는 리스트(List), 아직 방문하지 않은 노드를 저장하는 데는 FIFO방식의 큐(Queue)를 사용해 구현할 수 있다.
1) 레벨 순회 (Level-order traversal)
