[알고리즘] DFS & DFS

BFS & DFS

정말 좋은 영상입니다.

 

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

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

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

 

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

 

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

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

[자료구조 알고리즘] 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가 비워질 때 까지 반복한다.