[그래프]우선 깊이 탐색(DFS)과 우선 너비 탐색(BFS)

*주의*해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다.

• 알고리즘 유형 : 그래프 탐색 기본
• 출처 링크 : https://velog.io/@jewon119/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS
• 출처 링크 : https://lgphone.tistory.com/93

알고리즘 기초 - 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS)

---

그래프 탐색 기본

- 그래프의 개념은 내일 다시 정리 예정

---

깊이 우선 탐색(depth-first search, DFS)

    1) 전위 순회(pre-order traversal)
        - 순서 : 루트 노드 >>> 왼쪽 노드 >>> 오른쪽 노드 순으로 방문한다. 
        - 코드 : 

def preorder(root):
    if root != 0:
        yield root.value
        preorder(root.left)
        preorder(root.right)

    2) 중위 순회(in-order traversal)
        - 순서 : 왼쪽 노드 >>> 루트 노드 >>> 오른쪽 노드 순으로 방문한다.
        - 코드 : 

def inorder(root):
    if root != 0:
        inorder(root.left)
        yield root.value
        inorder(root.right)

    3) 후위 순회(post-order traversal)
        - 순서 : 왼쪽 노드 >>> 오른쪽 노드 >>> 루트 노드 순으로 방문한다.
        - 코드 :

def postorder(root):
    if root != 0:
        postorder(root.left)
        postorder(root.right)
        yield root.value

 

 

---

너비 우선 탐색(breadth-first search, BFS)

    1) 탐색 순서
        - 계단식으로 해당 Node와 같은 레벨에 있는 형제노드를 먼저 탐색

    2) 두개의 queue가 필요
        - need_visit : 방문 예정(순서가 매겨진)인 방문 대기 queue
        - visited : 이미 방문 한 (순차적으로) 방문 완료 queue

    3) 갈 수 있는 곳을 방문대기 queue에 넣고 queue의 앞부터 하나씩 빼서 탐색