ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 알고리즘: DFS, BFS (너비우선탐색, 깊이우선탐색)
    알고리즘 2024. 6. 6. 18:04

    각 알고리즘의 탐색방식

    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는 특정 조건을 만족하는 경로를 찾는 데 유리함.
Designed by Tistory.