DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

탐색 알고리즘

주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘

 

---

 

DFS(깊이 우선 탐색) 알고리즘

* DFS : Depth-First Search

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

• 기능

- 그래프 완전 탐색 기법

 

• 특징

- 재귀 함수로 구현

- 스택 자료구조 이용 (스택 오버플로에 유의)

 

스택(Stack)과 큐(Queue) 자료구조

스택(Stack)과 큐(Queue) 자료구조

 

• 시간 복잡도(노드 수 : V, 에지 수 : E)

- O(V + E)

 

• 응용 문제

- 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등

 

 

DFS의 핵심 이론

1. DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화한다.

[ DFS 예시 ]

 

- 인접 리스트로 그래프 표현하기

- 방문 배열 초기화하기

- 시작 노드 스택에 삽입하기

 

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

[ DFS 예시 ]

 

- pop을 수행하여 스택에서 노드를 꺼낼 때, 꺼낸 노드를 탐색 순서에 기록한다.

- 대상 노드의 인접 노드를 스택에 삽입할 때, 방문 배열을 체크한다.

[ 예시 ]

- 탐색 순서 : 1

- 방문 배열 : T, T, T, F, F, F

 

3. 2번의 과정을 스택 자료구조에 값이 없을 때까지 반복한다.

[ DFS 예시 ]

 

- 방문 배열을 체크하여 이미 방문한 노드는 스택에 재삽입하지 않는다.

 

[ 예시 ]

- 탐색 순서 : 1 → 3 → 4 → 6 → 2 → 5

- 방문 배열 : T, T, T, T, T, T

 

 

DFS 구현

void DFS(int v)
{
  if(visited[v])
  {
    return ;
  }
  
  visited[v] = true;
  
  for(int i : A[v])
  {
    if(visited[i] == false)	// 연결 노드 중 방문하지 않은 노드만 탐색함
    {
      DFS(i);
    }
  }
}

 

---

 

BFS(너비 우선 탐색) 알고리즘

* BFS : Breadth-First Search

가까운 노드부터 탐색하는 알고리즘

 

• 기능

- 그래프 완전 탐색 기법

 

• 특징

- FIFO 탐색

- 큐 자료구조 이용

- 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로 보장

 

스택(Stack)과 큐(Queue) 자료구조

스택(Stack)과 큐(Queue) 자료구조

 

• 시간 복잡도(노드 수 : V, 에지 수 : E)

- O(V + E)

 

 

BFS의 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화한다.

[ BFS 예시 ]

 

- 인접 리스트로 그래프 표현하기

- 방문 배열 초기화하기

- 시작 노드 큐에 삽입하기

 

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

[ BFS 예시 ]

 

- pop을 수행하여 큐에서 노드를 꺼낼 때, 꺼낸 노드를 탐색 순서에 기록한다.

- 대상 노드의 인접 노드를 큐에 삽입할 때, 방문 배열을 체크한다.

[ 예시 ]

- 탐색 순서 : 1

- 방문 배열 : T, T, T, F, F, F

 

3. 2번의 과정을 큐 자료구조에 값이 없을 때까지 반복한다.

[ BFS 예시 ]

 

- 방문 배열을 체크하여 이미 방문한 노드는 큐에 재삽입하지 않는다.

 

[ 예시 ]

- 탐색 순서 : 1 → 2 → 3 → 5 → 6 → 4

- 방문 배열 : T, T, T, T, T, T

 

 

BFS 구현

void BFS(int v)
{
  queue<int> myqueue;
  myqueue.push(v);
  visited[v] = true;
  
  while(!myqueue.empty())
  {
    int now_node = myqueue.front();
    myqueue.pop();
    
    for(int i : A[now_node])
    {
      if(!visited[i])	// 연결 노드 중 방문하지 않은 노드만 탐색함
      {
      	visited[i] = true;
        myqueue.push(i);
      }
    }
  }
}

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.