[C++ 알고리즘] 무향그래프 사이클 dfs

dfs를 응용하여 무향그래프에서의 사이클을 판단할 수 있는 코드이다. 

 

간단하게 설명하자면 점을 하나씩 순회하며 사이클이 존재하는지 판별하는 코드이다.

 

예를 들어 아래와 같은 그래프가 있다고 하자.

 

눈으로 봐서는 2 3 5 사이클이 존재함을 알 수 있다. 아래 코드에서는 1에서부터 dfs를 하며 바로 사이클을 찾게 된다.

dfs 가장 아래 path.pop_back()은 4와 같이 사이클에 포함되지 않는 노드를 제거하는 코드이다. 인접한 노드가 전에 방문한 노드밖에 없을 때의 경우이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> graph; // 그래프 인접 리스트
vector<pair<int, int>> edges; // 간선 정보
vector<bool> visited;
vector<int> path;

bool dfs(int cur, int prev) {
    cout << "cur is " << cur << endl;
    path.push_back(cur);
    visited[cur] = true;
    for (auto k : graph[cur]) {
        if (!visited[k]) {
            if (dfs(k, cur))return true;
        }
        else if (k != prev) {
            path.push_back(k);
            return true;
        }
    }
    path.pop_back();
    return false;

}

vector<int> findCycle(int n) {
    for (int i = 1; i <= n; i++) {
        path.clear();
        vector<int> ans;
        if (dfs(i, -1)) {
            int start = path.back();
            while (!path.empty()) {
                int cur = path.back();
                path.pop_back();
                ans.push_back(cur);
                if (cur == start && ans.size() > 1) {
                    return ans;
                }
            }
        }
    }
    return {};
}
int main() {
    int n = 6; // 노드 수
    edges = { {1, 2}, {2, 3}, {3, 4}, {3, 5}, {5,2} };
    visited.assign(n, false);
    // 그래프 초기화
    graph.assign(n + 1, vector<int>());
    for (auto edge : edges) {
        graph[edge.first].push_back(edge.second);
        graph[edge.second].push_back(edge.first);
    }
    vector<int> vec = findCycle(n);

    if (!vec.empty()) {
        for (auto k : vec) {
            cout << k << " ";
        }
        cout << endl;
    }
    else {
        cout << "NO CYCLE\n";
    }


    return 0;
}

 

관련 문제를 풀어볼 수 있는 블로그

https://velog.io/@jeon0976/Data-Structure-Algorithms-Cycle-Detection-in-Graphs-%EC%82%AC%EC%9D%B4%ED%81%B4-%ED%8C%90%EB%B3%84