[자료구조] DFS (깊이우선탐색)과 BFS (너비우선탐색)

깊이-우선 탐색 (DFS : Depth-First Search) → Stack, recursion (재귀함수)로 구현

루트 노드 (혹은 다른 임의의 노드)에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식.

DFS를 이용해 탐색하는 경우
: 모든 노드를 방문하고자 하는 경우
: 깊이 우선 탐색이 너비우선탐색보다 간단
: 검색 속도 자체는 너비 우선 탐색에 비해 느리다

1. 출발 정점 v를 방문
2. v에 인접하고 방문하지 않은 한 정점 w를 선택
3. w를 시작점으로 다시 깊이 우선 탐색 시작 (recursion)
4. 어떤 정점 u에 갔는데 이미 모든 인접 정점을 방문했다면, 최근에 방문한 정점 중 아직 방문하지 않은 정점 w와 인접하고 있는 정점으로 되돌아감
5. 정점 w로부터 다시 깊이 우선 탐색 시작
6. 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료

virtual void Graph::DFS(){ // Driver
    visited = new bool [n]; //갔는지 안갔는지를 나타내는 boolean (true면 방문, false면 방문 X)
    fill(visited, visited+n, false); // 맨 처음엔 모두 안갔으니 false
    DFS(0); // vertex 0번부터 search 시작해봐
    delete [] visited; //
}

virtual void Graph::DFS(const int v){
    visited [v] = true;
    for (each vertex w adjacent to v)
        if(!visited[w]) // visited가 아니면
            DFS(w); // 다시 DFS를 실시해라 (깊이우선탐색)
}

Prf Q. 6번 노드에서 시작하면 노드 방문 순서는 ?
→ 6 - 2- 0 - 1 - 3 - 7 - 4 - 5

• DFS 의 분석
  • Adjacency list 사용한 경우 : 탐색을 끝내는 시간 O(e)
  • Adjacency matrix 사용한 경우
    : v에 인접한 모든 정점들을 찾는데 O(n) 시간
    : 총 시간은 O($n^2$)

너비 우선 탐색 BFS; Breadth-First Search → QUEUE 사용

루트 노드 (혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색.

BFS를 이용해 탐색하는 경우
: 두 노드 사이의 최단 경로를 찾고 싶을 때 해당 방법을 선택함

• 너비 우선 탐색
  • 시작 정점 v를 방문
  • v에 인접한 모든 정점들을 방문
  • 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문
    
  방문 순서 : 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 순서대로

virtual void Graph::BFS(int v)
// 너비 -우선 탐색은 정점 v에서부터 시작
// v 방문 시 visited[v]는 true로 설정된다. 이 함수는 큐를 사용함
{
    visited = new bool[n];
    fill(visited, visited + n, false); // 맨 처음엔 다 false 이다
    visited[v] = true; cout<<v<<" ";
    Queue<int> q; // q 만든다
    q.Push(v); // v를 큐에 집어넣는다
    
    while (!q.IsEmpty()){ // 큐가 비어있지 않는한,
        v = q.Front();
        q.Pop(); //// 프론트에서 하나 꺼내서
        
    for (v에 인접한 모든 정점 w에 대해) // v에 인접한 모든 정점에 대해
        if(!visited[w]){ // visited가 아니면
            q.Push(w); // w에 넣고
            visited[w] = true;// w를 visit 했다고 만들어놓자
            
            // => 큐가 빌때까지 반복 
	   // 방문한 각 정점들은 큐에 오직 한 번만 들어가므로 while 루프는 최대 n번 반복됨 
        }
    } // while 루프 끝!
        
    delete[]visited;
}

• BFS의 분석
  • Adjacency matrix의 표현 : 전체 시간 O$(n^2)$
  • 인접 리스트 표현 : 전체비용 O(e)

---

• 그래프의 모든 정점을 방문하고자 하는 경우 → DFS, BFS 모두 사용 가능
• 경로의 특징을 저장하는 경우 → DFS 사용 (BFS는 경로의 특징 가지지 못함)
• 최단 거리를 구하고자 하는 경우 → BFS 사용 (현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이다)

( DFS, BFS 요약 자료참고) DFS, BFS의 설명, 차이점