[알고리즘] 전공 필기 시험 준비2

그래프·트리 순회

깊이 우선 탐색(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.value

 

2. 너비 우선 탐색(BFS, Breadth First Search)

• 깊이가 1인 노드들을 먼저 방문하고 나서, 그 다음에는 깊이가 2인 노드들, 깊이가 3인 노드들을 차례로 방문하다가 더이상 방문할 곳이 없으면 탐색을 마친다.
• 너비 우선 탐색은 그래프·트리 내 모든 노드를 방문하고 싶을 때, 찾는 것을 발견할 때까지 모든 노드를 적어도 한 번은 방문하고 싶을 때 사용하면 좋다.
• 방문한 노드를 저장하는 데는 리스트(List), 아직 방문하지 않은 노드를 저장하는 데는 FIFO방식의 큐(Queue)를 사용해 구현할 수 있다.

1) 레벨 순회 (Level-order traversal)

https://jocoma.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84%C2%B7%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89