Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 그래프 정점 커버(Vertex Cover) 휴리스틱 알고리즘

그래프 이론에서 정점 커버(Vertex Cover)란 그래프에 존재하는 모든 간선에 대해, 해당 간선이 연결하는 두 정점 M과 N 중 적어도 하나(또는 둘 다)가 반드시 포함되어 있는 정점들의 집합 V를 의미합니다. 즉, 집합 V에 속한 정점들이 그래프의 모든 간선을 '덮는(cover)' 것입니다.

이 글에서는 그래프의 정점 커버를 찾기 위한 휴리스틱(Heuristic) 알고리즘을 C++로 구현하는 방법을 살펴봅니다. 정점 커버 문제는 NP-완전 문제로 알려져 있어 최적해를 다항 시간에 구하기 어렵기 때문에, 실제로는 근사해를 빠르게 찾는 휴리스틱 기법이 널리 활용됩니다.

알고리즘 동작 원리

이 휴리스틱은 탐욕적(Greedy) 방식으로 동작합니다. 아직 처리하지 않은 임의의 간선을 하나 선택하고, 그 양 끝점을 모두 결과 집합에 추가한 뒤, 두 정점과 연결된 모든 간선을 제거하는 과정을 반복합니다.

Begin
    1) 집합 S를 공집합으로 초기화한다.
    2) 그래프에서 아직 남아 있는 간선 E(연결 정점 M, N)를 하나 선택한다.
    3) 정점 M과 N을 모두 집합 S에 추가한다.
    4) M 또는 N을 끝점으로 가지는 모든 간선을 그래프에서 제거한다.
    5) 그래프에 간선이 남아 있다면 2)단계로 돌아간다.
    6) 최종 집합 S를 그래프의 정점 커버로 출력한다.
End

이 방식은 선택된 간선의 양쪽 끝점을 모두 포함하므로, 최종적으로 만들어지는 집합은 항상 유효한 정점 커버가 됩니다. 다만 최소 크기의 정점 커버임을 보장하지는 않으며, 일반적으로 최적해의 2배 이내 크기를 갖는 것이 알려져 있습니다.

C++ 구현 코드

아래 코드는 인접 리스트 형태로 그래프를 저장하고, 방문 여부 배열(v)을 활용해 위 알고리즘을 구현한 예제입니다.

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
bool v[11110];
int i,j;
vector<int> sol_vertex(int n,int e) {
    vector<int> S;
    for(i=0;i<n;i++) {
        if(!v[i]) {
            for(j=0;j<(int)g[i].size();j++) {
                if(!v[g[i][j]]) {
                    v[i]=true;
                    v[g[i][j]]=true;
                    break;
                }
            }
        }
    }
    for(i=0;i<n;i++)
        if(v[i])
            S.push_back(i);
    return S;
}
int main() {
    int n,e,a,b;
    cout<<"Enter number of vertices:";
    cin>>n;
    cout<<"Enter number of Edges:";
    cin>>e;
    g.resize(n);
    memset(v,0,sizeof(v));
    for(i=0;i<e;i++) {
        cout<<"Enter the end-points of edge "<<i+1<<" : ";
        cin>>a>>b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> S = sol_vertex(n,e);
    cout<<"The required vertex cover is as follows:\n";
    for(i=0;i<(int)S.size();i++)
        cout<<S[i]+1<<" ";
    return 0;
}

코드 설명

  • g: 무방향 그래프를 저장하는 인접 리스트입니다. 간선 입력 시 양방향으로 추가됩니다.
  • v: 각 정점이 정점 커버 집합에 포함되었는지(방문되었는지)를 나타내는 불리언 배열입니다.
  • sol_vertex 함수: 각 정점을 순회하며 아직 방문하지 않은 정점 i에 대해, i와 연결된 미방문 정점이 존재하면 두 정점을 모두 방문 처리합니다. 이것이 곧 간선의 양 끝점을 집합 S에 추가하는 과정에 해당합니다.
  • 출력 부분: 방문 처리된 정점들을 모아 벡터 S에 담아 반환하며, main 함수에서 1부터 시작하는 정점 번호로 출력합니다.

실행 결과

4개의 정점과 5개의 간선으로 구성된 그래프를 입력했을 때의 실행 결과는 다음과 같습니다.

Enter number of vertices:4
Enter number of Edges:5
Enter the end-points of edge 1 : 2 1
Enter the end-points of edge 2 : 3 2
Enter the end-points of edge 3 : 4 3
Enter the end-points of edge 4 : 1 4
Enter the end-points of edge 5 : 1 3
The required vertex cover is as follows:
1 2 3 4

입력된 그래프는 4개 정점이 사이클과 대각선 간선으로 밀집된 형태이므로, 모든 간선을 덮기 위해 정점 {1, 2, 3, 4} 전체가 정점 커버로 선택된 것을 확인할 수 있습니다.