[c++] 그래프의 연결 여부 확인 알고리즘

08 Dec 2023

그래프에서 모든 정점이 서로 연결되어 있는지를 확인하는 것은 매우 중요합니다. 이를 확인하는 알고리즘 중 하나는 깊이 우선 탐색(DFS)을 사용하는 것입니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색은 한 정점으로부터 시작하여 그래프의 모든 정점을 방문하는 알고리즘입니다. 이를 통해 그래프의 연결 여부를 확인할 수 있습니다. 그래프의 모든 정점을 방문하는 과정에서, 한 번도 방문되지 않은 정점이 있으면 그래프는 연결되어 있지 않다고 판단할 수 있습니다.

아래는 C++에서의 간단한 깊이 우선 탐색 알고리즘 예시입니다.

#include <iostream>
#include <vector>

void dfs(int v, std::vector<bool>& visited, std::vector<std::vector<int>>& graph) {
    visited[v] = true;
    for (int u : graph[v]) {
        if (!visited[u]) {
            dfs(u, visited, graph);
        }
    }
}

bool isConnected(std::vector<std::vector<int>>& graph) {
    int n = graph.size();   // 그래프의 정점 개수
    std::vector<bool> visited(n, false);   // 방문 여부를 저장하는 배열

    dfs(0, visited, graph);   // 첫 번째 정점부터 깊이 우선 탐색 시작

    for (bool v : visited) {
        if (!v) {   // 방문되지 않은 정점이 있으면 그래프는 연결되어 있지 않다고 판단
            return false;
        }
    }
    return true;   // 모든 정점을 방문했을 경우 그래프는 연결되어 있다고 판단
}

int main() {
    std::vector<std::vector<int>> graph = {{1, 2}, {0, 2}, {0, 1}};   // 간단한 그래프 예시
    bool connected = isConnected(graph);
    std::cout << "The graph is " << (connected ? "connected" : "not connected") << std::endl;
    return 0;
}

위의 코드는 인접 리스트 형태의 그래프를 입력으로 받아 해당 그래프가 연결되어 있는지를 판단하는 것을 보여줍니다.

그래프의 연결 여부를 확인하는 것은 그래프 이론이나 알고리즘 관련 문제를 해결하는 데 매우 중요한데, 깊이 우선 탐색을 이용한 알고리즘은 이러한 문제를 해결하는 데 유용하게 활용됩니다.