Chương trình C++ xóa cạnh trong đồ thị chu trình để tìm mở rộng tuyến tính

Chương trình này tìm tập cung phản hồi (feedback arc set) chứa các cạnh mà khi xóa đi, đồ thị trở thành đồ thị có hướng không chu trình (DAG).

Thuật toán

Bắt đầu
  hàm checkCG(int n):
    n: số đỉnh. arr: cấu trúc đồ thị.
    Khởi tạo cnt = 0, size = n-1.
    Với i = 0 đến n-1:
       Nếu cnt == size trả về 0.
       Nếu arr[i].ptr == NULL: tăng cnt, xóa các cạnh trùng.
    Khởi tạo visited[n+1].
    Với i = 0 đến n-1:
       Duyệt danh sách kề, in đỉnh, đánh dấu visited.
       Với j = 0 đến n-1: in các cạnh, nếu visited thì in cặp.
    Trả về 1.
Kết thúc

Ví dụ

#include <iostream>
using namespace std;
int c = 0;
struct ad_list {
    int des;
    ad_list *next;
} *np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
struct Graph {
    int v;
    ad_list *ptr;
} arr[6];

void addRevEdge(int sr, int des) { ... }
void addEd(int sr, int des) { ... }
void print_graph(int n) { ... }

int checkCG(int n) {
    int cnt = 0, size = n - 1;
    for (int i = 0; i < n; i++) {
        if (cnt == size) return 0;
        if (arr[i].ptr == NULL) {
            cnt++;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    if ((arr[j].ptr)->des == (arr[i].ptr)->des)
                        (arr[j].ptr)->des = -1;
                    arr[i].ptr = (arr[i].ptr)->next;
                }
            }
        }
    }
    cout << "after checking dag";
    int visited[n + 1];
    for (int i = 0; i < n; i++) {
        while (arr[i].ptr != NULL) {
            cout << (arr[i].ptr)->des << " ";
            visited[i] = 1;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    cout << (arr[j].ptr)->des << " ";
                    if (visited[arr[j].v] == 1)
                        cout << arr[i].v << " - " << arr[j].v;
                    arr[j].ptr = (arr[j].ptr)->next;
                }
                cout << endl;
            }
            arr[i].ptr = (arr[i].ptr)->next;
        }
        cout << endl;
    }
    return 1;
}

int main() {
    int n = 5;
    cout << "Number of vertices: " << n << endl;
    for (int i = 0; i < n; i++) {
        arr[i].v = i;
        arr[i].ptr = NULL;
    }
    addEd(1, 2); addEd(2, 1); addEd(0, 1);
    addEd(2, 3); addEd(2, 0); addEd(5, 4); addEd(4, 2);
    print_graph(n);
    cout << "Feedback arc Set: ";
    if (checkCG(n) == 0) cout << " None";
}

Kết quả

Number of vertices: 5
Adjacency List of 0: 1
Adjacency List of 1: 2
Adjacency List of 2: 1 3 0
Adjacency List of 3:
Adjacency List of 4: 2
Feedback arc Set: None