[알고리즘] BFS, DFS

< BFS(Breadth First Search) >

• 너비 우선 탐색
• 루트 노드가 자식 노드들을 먼저 차례로 방문후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식
• 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 '큐' 를 활용함

 

---

BFS()

    큐 생성

    루트 v를 큐에 삽입

    while(큐가 비어 있지 않은 경우) {

        t = 큐의 첫 번쨰 원소 반환

        t 방문

        for(t와 연결된 모든 간선에 대해) {

           u = t의 자식 노드

           u를 큐에 삽입

        }

    }

end BFS()

---

< DFS(Depth First Search) >

• 깊이 우선 탐색
• 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복.
• 재귀 or 후입선출인 스택 사용

---

DFS(v)

    v 방문;

    for(v의 모든 자식 노드 w) {

        DFS(w);

    }

end DFS()