Chương trình C++ giải bài toán tập điều khiển (Dominating Set)

Tập điều khiển (Dominating Set) của đồ thị là tập hợp các đỉnh sao cho mọi đỉnh không trong tập đều kề với ít nhất một đỉnh trong tập. Chương trình tìm một tập điều khiển (không nhất thiết tối thiểu) bằng thuật toán tham lam.

Thuật toán

Bắt đầu
  Nhập số đỉnh (v) và số cạnh (e), danh sách cạnh.
  Hàm dominant():
    Khởi tạo mảng visited[] = false.
    Với mỗi đỉnh i từ 0 đến v-1:
      Nếu chưa thăm:
        Thêm i vào tập kết quả.
        Đánh dấu i đã thăm.
        Với mỗi đỉnh kề j của i:
          Nếu j chưa thăm: đánh dấu j đã thăm và thoát vòng lặp con.
    Trả về tập kết quả.
Kết thúc

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graph;
bool visited[10001];

vector<int> dominant(int v, int e) {
    vector<int> domSet;
    for (int i = 0; i < v; i++) {
        if (!visited[i]) {
            domSet.push_back(i);
            visited[i] = true;
            for (int j = 0; j < graph[i].size(); j++) {
                if (!visited[graph[i][j]]) {
                    visited[graph[i][j]] = true;
                    break;
                }
            }
        }
    }
    return domSet;
}

int main() {
    int v, e, a, b;
    cout << "So dinh: "; cin >> v;
    cout << "So canh: "; cin >> e;
    graph.resize(v);
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < e; i++) {
        cout << "Canh " << i+1 << ": ";
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<int> domSet = dominant(v, e);
    cout << "Tap dieu khien: ";
    for (int x : domSet) cout << x+1 << " ";
    return 0;
}

Đầu ra mẫu

So dinh: 7
So canh: 6
Canh 1: 1 2
Canh 2: 2 3
Canh 3: 3 4
Canh 4: 4 5
Canh 5: 6 7
Canh 6: 4 5
Tap dieu khien: 1 3 5 6