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

각 알고리즘의 탐색방식

DFS와 BFS는 그래프를 탐색하는 알고리즘이다.

---

DFS(Depth-First Search)

DFS는 그래프를 깊이 우선으로 탐색한다. 즉, 시작 노드에서 시작하여 한 갈래를 끝까지 탐색한 후에 다른 갈래를 탐색한다.

구현 방법

스택이나 재귀함수로 구현한다.

동작 과정

1. 시작 노드를 스택에 넣는다.
   • 예를 들어, 시작 노드가 A라고 하자. 처음에는 스택에 A만 들어 있다.
   • 스택: [A]
2. 스택에서 노드를 하나 꺼내어 방문한다.
   • 스택에서 A를 꺼내어 방문한다.
   • 방문한 노드: A
   • 스택: []
3. 방문한 노드의 인접 노드 중 방문하지 않은 노드를 스택에 넣는다.
   • 예를 들어, A의 인접 노드가 B와 C라면, 이들을 스택에 넣는다.
   • 스택: [B, C]
4. 스택이 빌 때까지 2-3 단계를 반복한다.
   • 다음으로, 스택에서 C를 꺼내어 방문한다.
   • 방문한 노드: A, C
   • 스택: [B]
   • C의 인접 노드 중 방문하지 않은 노드를 스택에 넣는다. (C의 인접 노드가 D라면, 스택에 D를 넣음.)
   • 스택: [B, D]
   • 계속해서 이 과정을 반복한다.

구현 in C++:

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w);
    void DFS(int start);

private:
    int vertices;                // 노드의 수
    vector<vector<int>> adjList; // 인접 리스트
};

// 생성자
Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

// 간선 추가
void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w); // 유향 그래프
    adjList[w].push_back(v); // 무향 그래프일 경우 사용, 아니면 삭제
}

// DFS 구현
void Graph::DFS(int start) {
    vector<bool> visited(vertices, false); // 방문 여부를 추적
    stack<int> stack;
    
    stack.push(start);
    
    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();
        
        if (!visited[node]) {
            cout << node << " ";
            visited[node] = true;
        }
        
        for (auto i = adjList[node].rbegin(); i != adjList[node].rend(); ++i) {
            if (!visited[*i]) {
                stack.push(*i);
            }
        }
    }
}

int main() {
    Graph g(5); // 5개의 노드를 가진 그래프
    
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(3, 4);
    
    cout << "Depth First Traversal (starting from node 0): ";
    g.DFS(0);
    
    return 0;
}

 

1. 그래프 class를 만든다. (무향) 
   • 노드의 수를 매개변수로 생성한다.
   • addEdge(node1, node2) 메소드로 node1에 node2가 연결되어 있음을 명시한다.
   • adjList는 2차원 배열을 생각하면 된다. (adjList[1]에 2를 push하면 1에 2가 연결되어 있음을 뜻함.)
2. main에서 addEdge로 그래프를 하나 만든다.
   • 0 - 2
   • |      |
   • 1 --
   • |
   • 3
   • |
   • 4
   • adjList[0] = [1, 2]
   • adjList[1] = [0, 2, 3]
   • adjList[2] = [0, 1]
   • adjList[3] = [1, 4]
   • adjList[4] = [3]
3. DFS를 구현한다.
   • visited(0, 0, 0, 0, 0)와 stack을 하나 만들어 시작노드를 push하고 시작한다.
   • stack의 top을 visited에 기록하고 pop하며 adjList를 확인하여 인접 노드를 전부 stack에 푸시하고 표시한다.
   • stack인 경우 FILO형식이기 때문에 adjList는 역순으로 순회하게 된다. rbegin(), rend() 
   • stack이 empty가 될 때까지 반복한다. (visited가 전부 1이 될때까지 반복해도 될거 같은데?)
   • 스택이 비어질 때까지 반복하는 방식이 일반적으로 더 간단하고 효율적입니다. visited 배열이 모두 true가 될 때까지 반복하는 방법도 가능하지만, 불필요한 추가 연산이 발생할 수 있습니다. 따라서 DFS에서는 스택을 사용하여 반복하는 것이 더 적합합니다. -by GPT 3.5

특징

• 시간 복잡도: O(V + E), 여기서 V는 노드의 수, E는 간선의 수이다.
• 공간 복잡도: O(V) (재귀 호출로 인한 호출 스택 포함)
• 용도: 경로 탐색, 사이클 탐지, 위상 정렬 등.

---

BFS(Breadth-First Search)

BFS는 그래프를 너비 우선으로 탐색한다.

즉, 시작 노드에서 시작하여 모든 인접 노드를 먼저 탐색하고, 그 다음으로 인접 노드의 인접 노드를 탐색한다.

구현 방법

큐를 사용하여 구현한다.

동작 과정

1. 시작 노드를 큐에 넣는다.
2. 큐에서 노드를 하나 꺼내어 방문한다.
3. 방문한 노드의 인접 노드 중 방문하지 않은 노드를 큐에 넣는다.
4. 큐가 빌 때까지 2-3 단계를 반복한다.

구현 in C++:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

class Graph
{
public:
    Graph(int vertices);
    void addEdge(int v, int w);
    void DFS(int start);
    void BFS(int start);

private:
    int vertices;                // 노드의 수
    vector<vector<int>> adjList; // 인접 리스트
};

// 생성자
Graph::Graph(int vertices)
{
    this->vertices = vertices;
    adjList.resize(vertices);
}

// 간선 추가
void Graph::addEdge(int v, int w)
{
    adjList[v].push_back(w); // 방향성 있는 그래프
    adjList[w].push_back(v); // 방향성 없는 그래프일 경우 필요
}

void Graph::BFS(int start) {
    cout << "Depth First Traversal (starting from node 0):";
    vector<bool> visited(vertices, false); // 방문 여부를 추적
    queue<int> queue; // BFS에 사용할 큐

    visited[start] = true; // 시작 노드를 방문 표시
    queue.push(start);

    while (!queue.empty()) {
        int node = queue.front(); // 큐의 앞에서 노드를 가져옵니다.
        queue.pop();

        cout << node << " "; // 현재 노드를 출력합니다.

        // 인접한 모든 노드를 큐에 추가 (방문하지 않은 노드만)
        for (auto i = adjList[node].begin(); i != adjList[node].end(); ++i) {
            if (!visited[*i]) {
                visited[*i] = true; // 방문 표시
                queue.push(*i); // 큐에 추가
            }
        }
    }

    cout << "\n";
}

int main()
{
    Graph g(5); // 5개의 노드를 가진 그래프

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(3, 4);

    g.BFS(0);

    return 0;
}

1. 그래프의 구현은 DFS와 같다.
2. BFS를 구현한다.
   • visited(0, 0, 0, 0, 0)와 queue을 하나 만들어 시작노드를 push하고 시작한다.
   • queue의 top을 visited에 기록하고 pop하며 adjList를 확인하여 인접 노드를 전부 queue에 푸시하고 표시한다.
   • queue이 empty가 될 때까지 반복한다.

특징

• 시간 복잡도: O(V + E), 여기서 V는 노드의 수, E는 간선의 수 이다.
• 공간 복잡도: O(V)
• 용도: 최단 경로 탐색, 레벨 순회, 연결 요소 찾기 등.

---

차이점

• 탐색 순서: DFS는 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 반면, BFS는 모든 인접 노드를 탐색한 후 다음 단계로 넘어감.
• 구현 구조: DFS는 스택 또는 재귀를 사용하고, BFS는 큐를 사용함.
• 특성: BFS는 최단 경로를 찾는 데 적합하고, DFS는 특정 조건을 만족하는 경로를 찾는 데 유리함.