[알고리즘/C++] - 그래프/BFS 와 DFS

이전 글에 이어서 그래프의 종류 중 하나인 BFS,DFS를 알아보도록 하겠습니다.

사실 이야기하자면 DFS와 BFS는 그래프보다는 그래프 탐색기법이라고 생각하셔야 합니다.

먼저 이전시간에서 그래프의 정의만 알아보고 그래프를 구현하는 방법에 대해서 알아보지 않았었는데, 

그래프를 구현하는 구조 세가지를 알아보도록 하겠습니다. 

 

연결선 리스트

:간선을 중심으로 그래프를 나타내는 방식입니다.

• 각 노드에 대해 인접한 노드들의 리스트를 유지하는 구조입니다.
• 간선 수에 비례하여 공간을 사용하므로 희소 그래프에 자주 활용됩니다.
• 각 간선을 (u,v)형태로 저장하며 그래프의 간선들을 리스트로 표현하기에 단순한 구조를 가집니다.
• 그래프의 간선 개수가 중요할 때 사용되며, 간선 기반 연산에 유리합니다.
• 반두 노드의 연결 여부를 확인하기 위해 리스트 전체를 탐색해야 하기에 O(n)의 시간이 걸립려 비효율적입니다.

인접행렬

: 노드 간의 연결 상태를 2차원 배열로 표현합니다. 각 배열의 원소 (i,j)가 노드 i와 j사이의 간선 여부를 나타냅니다.

•  2차원 배열로, (i, j) 원소가 노드 i와 노드 j 간의 간선의 존재 여부를 나타냅니다.
• 모든 노드 싼에 대해 간선 존재 여부를 기록합니다. 때문에 노드 수가 많을 수록 공간낭비가 가장 심한 편입니다.
• 인접행렬을 사용하면 두 노드 간의 연결 여부를 상수 시간 O(1)으로 확인할 수 있기에 굉장히 빠른 노드 탐색 속도를 보입니다.
• 간선 추가 및 삭제가 O(1)로 가능합니다.
• 반면, 특정 노드의 이웃을 찾는 과정에서는 해당 노드와 연결된 모든 노드를 확인해야 하기 때문에 시간 복잡도가 O(n)으로 확연히 느려집니다.
• 두 노드 간의 연결 여부를 O(1)로 확인할 수 있기에 밀집 그래프에서 적합합니다.

 

인접리스트

: 각 노드에 대해 인접한 노드들을 리스트 형태로 저장하는 방식입니다.

• 인접 행렬과 반대로 노드 중심의 연산에서 각 노드의 이웃을 효율적으로 탐색한다는 특징이 있어 희소 그래프에서 적합합니다.
• 그래프가 희소한 경우에 인접리스트는 필요한 만큼의 공간만 사용하기 때문에 메모리 효율이 뛰어난 편입니다. 
• 두 노드 간의 연결 여부를 확인하는 과정에서 각 노드의 리스트를 순차적으로 확인해야 하기때문에 노드수가 많으면 많을수록 탐색속도가 상대적으로 느릴 수 있습니다.

 

 

+여기서 배운 세가지 중, 대표적인 그래프 구현 방법으로는 인접행렬과 인접리스트를 뽑고는 합니다.

글만 보면 이해가 잘 안될 것 같으니,, 아래 개념과 예제를 보며 한 번 더 익혀보도록 합시다!

---

이제 위에서 배운 그래프 구현 방법 세가지를 활용하여 DFS,BFS를 구현해보도록 하겠습니다.

DFS

: 깊이 우선 탐색으로, 하나의 지점에서 시작하여 다른 가지로 넘어가기 전에 해당 기지의 경우의 수를 완벽하게 탐색하는 방법

특징

• 자기 자신을 호출하는 재귀성의 알고리즘입니다.
• 노드 방문여부를 잘못 검사하는 경우에는 무한루프에 빠질 수 있습니다.
• 현재 경로의 노드만 기억하면 되므로 저장 공간을 절약할 수 있습니다.
• 목표 노드가 깊게 자리할 경우 해를 구하기가 쉽습니다.
• 해가 없는 경로에서 해가 없다고 도출하기까지 오랜 시간이 걸립니다. 일단 시작하면 끝장을 보므로,,

이전 그래프의 특징에 따라, 총 세가지 (연걸선 리스트, 인접 리스트, 인접행렬)의 방법으로 DFS를 구현할 수 있습니다.

아래는 DFS구현을 C++로 진행한 코드입니다.

 

연결선 리스트를 활용한 DFS

void DFS(int start, const vector<pair<int, int>>& edges, int V) 
{
    vector<bool> visited(V, false);
    stack<int> s;
    s.push(start);

    while (!s.empty()) 
    {
        int node = s.top();
        s.pop();

        if (!visited[node]) 
        {
            cout << node << " ";
            visited[node] = true;
        }

        for (const auto& edge : edges) 
        {
            if (edge.first == node && !visited[edge.second]) 
            {
                s.push(edge.second);
            }
        }
    }
}

 

인접 리스트를 활용한 DFS

void DFS(int start, const vector<vector<int>>& adj_list)
{
    int V = adj_list.size();
    vector<bool> visited(V, false);
    stack<int> s;
    s.push(start);

    while (!s.empty())
    {
        int node = s.top();
        s.pop();

        if (!visited[node])
        {
            cout << node << " ";
            visited[node] = true;
        }

        for (int neighbor : adj_list[node])
        {
            if (!visited[neighbor])
            {
                s.push(neighbor);
            }
        }
    }
}

 

 

인접행렬을 활용한 DFS

void DFS(int start, const vector<vector<int>>& adj_matrix) 
{
    int V = adj_matrix.size();
    vector<bool> visited(V, false);
    stack<int> s;
    s.push(start);

    while (!s.empty()) 
    {
        int node = s.top();
        s.pop();

        if (!visited[node]) 
        {
            cout << node << " ";
            visited[node] = true;
        }

        for (int i = 0; i < V; ++i) 
        {
            if (adj_matrix[node][i] && !visited[i]) {
                s.push(i);
            }
        }
    }
}

---

 

BFS

: 너비 우선 탐색으로,DFS와 달리 인접한 여러가지들을 넓게 탐색하고 차근차근 안으로 들어가는 탐색법(?) 쉽게 말해, DFS는 김씨자손의자손의자손들까지 보고 이씨자손의자손의자손들까지 본다면, BFS는 김씨의 자손과 이씨의 자손을 보고 난 후, 김씨의자손의자손을보고 이씨의자손의자손을보며, 그 후에는 김씨의자손의자손의자손과.. 여기까지 하도록 하겠습니다..

 

특징

• 모든 경우의 가지를 동시에 시작합니다.
• 재귀를 사용하지 않습니다.
• 경로가 길 경우에는 많은 메모리를 필요로 합니다.

BFS또한 DFS와 같이 세가지의 방법으로 구현이 가능합니다.

아래는 BFS구현을 C++로 진행한 코드입니다.

 

연결선 리스트를 활용한 BFS

void BFS(int start, const vector<pair<int, int>>& edges, int V) 
{
    vector<bool> visited(V, false);
    queue<int> q;
    q.push(start);

    while (!q.empty()) 
    {
        int node = q.front();
        q.pop();

        if (!visited[node]) 
        {
            cout << node << " ";
            visited[node] = true;
        }

        for (const auto& edge : edges) 
        {
            if (edge.first == node && !visited[edge.second]) 
            {
                q.push(edge.second);
            }
        }
    }
}

인접 리스트를 활용한 BFS

void BFS(int start, const vector<vector<int>>& adj_list) 
{
    int V = adj_list.size();
    vector<bool> visited(V, false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) 
    {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : adj_list[node]) 
        {
            if (!visited[neighbor]) 
            {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

인접 행렬을활용한 BFS

void BFS(int start, const vector<vector<int>>& adj_matrix) 
{
    int V = adj_matrix.size();
    vector<bool> visited(V, false);
    queue<int> q;
    q.push(start);

    while (!q.empty()) 
    {
        int node = q.front();
        q.pop();

        if (!visited[node]) 
        {
            cout << node << " ";
            visited[node] = true;
        }

        for (int i = 0; i < V; ++i) 
        {
            if (adj_matrix[node][i] && !visited[i]) 
            {
                q.push(i);
            }
        }
    }
}

 

 

미묘하게 다른 점들을 보면 각각의 구조의 특징을 따라 구현되었다는 것을 느낄 수 있습니다.

그럼 오늘은 여기까쥐 하겄습니다~~~

---

반응형

참고자료

 

https://jud00.tistory.com/entry/Data-Structure-%EC%84%A0%ED%98%95Linear-%EB%B9%84%EC%84%A0%ED%98%95NonLinear-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0