Chương trình C++ tìm tập bao đỉnh (Vertex Cover) của đồ thị bằng heuristic

Tập bao đỉnh (Vertex Cover) của đồ thị là tìm tập đỉnh V sao cho với mọi cạnh nối M-N trong đồ thị, ít nhất M hoặc N (hoặc cả hai) thuộc V. Chương trình này triển khai thuật toán heuristic để tìm Vertex Cover.

Thuật toán

Bắt đầu
  1) Khởi tạo tập S rỗng.
  2) Lấy một cạnh E của đồ thị nối M và N.
  3) Thêm cả hai đỉnh vào tập S.
  4) Loại bỏ tất cả cạnh có đầu mút tại M hoặc N.
  5) Nếu còn cạnh trong đồ thị, quay lại bước 2.
  6) In tập S cuối cùng là vertex cover của đồ thị.
Kết thúc

Ví dụ mã nguồn

#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 << "Nhập số đỉnh: ";
    cin >> n;
    cout << "Nhập số cạnh: ";
    cin >> e;
    g.resize(n);
    memset(v, 0, sizeof(v));
    for (i = 0; i < e; i++) {
        cout << "Nhập đầu mút của cạnh " << 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 << "Tập bao đỉnh yêu cầu như sau:\n";
    for (i = 0; i < (int)S.size(); i++)
        cout << S[i]+1 << " ";
    return 0;
}

Kết quả

Nhập số đỉnh: 4
Nhập số cạnh: 5
Nhập đầu mút của cạnh 1 : 2 1
Nhập đầu mút của cạnh 2 : 3 2
Nhập đầu mút của cạnh 3 : 4 3
Nhập đầu mút của cạnh 4 : 1 4
Nhập đầu mút của cạnh 5 : 1 3
Tập bao đỉnh yêu cầu như sau:
1 2 3 4