티스토리 뷰

Programming/Algorithm

[알고리즘] DFS & DFS

나는 devssun 2020. 4. 6. 15:48

BFS & DFS

정말 좋은 영상입니다.

 

1. 깊이 우선 탐색(DFS: Depth-First Search)

노드를 방문할 때 마다 인접한 노드를 모두 방문한다., Stack 이나 재귀로 구현
모든 경로를 방문해야 할 경우 사용에 적합

https://upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif

[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java - 영상 캡쳐

 

[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java - 영상 캡쳐

 

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

레벨 단위로 노드를 방문한다., Queue로 구현
최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합

https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif

[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java - 영상 캡쳐

3. DFS & BFS를 슈도 코드로 나타내기

  • 깊이우선탐색(DFS)

        // DFS - pseudo code
        // 1. 시작할 노드를 스택에 push 한다.
        // 2. 스택에서 노드를 하나 pop한다.
        // 3. If pop한 노드와 인접한 노드가 있는 지 확인한다.
            // 3-1. pop한 노드와 인접한 노드를 스택에 push한다. (이미 push/pop 했던 노드는 push하지 않는다.)
        // 4. else pop한 노드를 출력한다.
        // 5. 2번부터 Queue가 비워질 때 까지 반복한다.
        // DFS with Recursion
        // 1. 현재 노드가 null 이면 종료한다.
        // 2. 현재 노드를 출력한다.
        // 2. If pop한 노드와 인접한 노드가 있는 지 확인한다.
            // 2-1. 재귀 함수를 호출하여 현재 노드를 매개변수로 넘긴다.
  • 너비우선탐색(BFS)

        /// BFS - pseudo code
        // 1. 시작할 노드를 Queue에 push 한다.
        // 2. Queue에서 노드를 하나 pop 한다.
        // 3. If pop한 노드와 인접한 노드가 있는 지 확인한다.
            // 3-1. pop한 노드와 인접한 노드를 스택에 push한다. (이미 push/pop 했던 노드는 push하지 않는다.)
        // 4. else pop한 노드를 출력한다.
        // 5. 2번부터 Queue가 비워질 때 까지 반복한다.
도움이 되셨다면.. Buy me a coffeeBuy me a coffee
댓글
댓글쓰기 폼