그래프·트리 순회(깊이우선탐색, 너비우선탐색)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다

목차

• <그래프·트리 순회>
  
• 깊이 우선 탐색(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)