책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다
목차
- <그래프·트리 순회>
- 깊이 우선 탐색(DFT, Depth First Search)
- DFS의 순회
- 너비 우선 탐색(BFS, Breadth First Search)
- BFS의 순회
<그래프·트리 순회>
순회 알고리즘은 그래프·트리에 저장된 모든 값을 중복이나 빠짐없이 살펴보고 싶을 때 사용한다.
순회 방법 중 깊이 우선 탐색(DFT, Depth First Search)으로는 전위 순회(Pre-order traversal), 정위 순회(In-order traversal), 후위 순회(Post-order traversal)가 있으며, 너비 우선 탐색(Breadth First Search)으로는 레벨 순회가 있다.
깊이 우선 탐색(DFT, Depth First Search)
- 진행 가능한 노드가 없을 때까지 깊게 파고들며 탐색하는 방식
- 더이상 방문 가능한 노드가 없다면 이전의 위치로 돌아와 다른 방향으로 깊게 파고들며 탐색한다.
- 과거 위치의 인접 노드보다 현재 위치의 인접 노드를 먼저 방문한다는 특징을 가지므로, LIFO방식의 스택(stack)을 사용해 구현할 수 있다.
DFS의 순회
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.value
너비 우선 탐색(BFS, Breadth First Search)
- 깊이가 1인 노드들을 먼저 방문하고 나서, 그 다음에는 깊이가 2인 노드들, 깊이가 3인 노드들을 차례로 방문하다가 더이상 방문할 곳이 없으면 탐색을 마친다.
- 너비 우선 탐색은 그래프·트리 내 모든 노드를 방문하고 싶을 때, 찾는 것을 발견할 때까지 모든 노드를 적어도 한 번은 방문하고 싶을 때 사용하면 좋다.
- 방문한 노드를 저장하는 데는 리스트(List), 아직 방문하지 않은 노드를 저장하는 데는 FIFO방식의 큐(Queue)를 사용해 구현할 수 있다.
BFS의 순회
레벨 순회 (Level-order traversal)
'⏳ 알고리즘 > python 알고리즘 개념' 카테고리의 다른 글
런너(runner) 기법이란?? (0) | 2021.05.09 |
---|---|
탐욕 알고리즘(Greedy) (0) | 2020.02.01 |
트리(3) - 자가 균형 이진 탐색 트리 (0) | 2020.01.20 |
트리(2) - 이진탐색트리 (0) | 2020.01.20 |
트리(1) - 이진트리 (0) | 2020.01.20 |