Chương trình C++ tìm tập cạnh phản hồi tốt trong đồ thị

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

Thuật toán

Begin function checkCG(int n) : n: số đỉnh. arr: biến struct graph. Khởi tạo cnt = 0 và size = (n-1). For i =0 to n-1    if (cnt == size)       return 0    if (arr[i].ptr == NULL)       Tăng cnt.       for j = 0 to n-1          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          Done       Done    Done Done initialize visited[n + 1] For i = 0 to n-1    while (arr[i].ptr != NULL)       Print (arr[i].ptr)->des       visited[i] = 1       for j = 0 to n-1          while (arr[j].ptr != NULL)             print (arr[j].ptr)->des             if (visited[arr[j].v] == 1)                print arr[i].v << " - " << arr[j].v             Done             arr[j].ptr = (arr[j].ptr)->next          Done       Done       arr[i].ptr = (arr[i].ptr)->next    Done Done return 1 End

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; } array[6]; void addRevEdge(int sr, int des) { //thêm cạnh ngược vào đồ thị    np1 = new ad_list;    np1->des = sr;    np1->next = NULL;    if (arr[des].ptr == NULL) {       arr[des].ptr = np1;       q = arr[des].ptr;       q->next = NULL;    } else {       q = arr[des].ptr;       while (q->next != NULL) {          q = q->next;       }       q->next = np1;    } } void addEd(int sr, int des) { // thêm cạnh vào đồ thị    np = new ad_list;    np->des = des;    np->next = NULL;    if (arr[sr].ptr == NULL) {       arr[sr].ptr = np;       p = arr[sr].ptr;       p->next = NULL;    } else {       p = arr[sr].ptr;       while (p->next != NULL) {          p = p->next;       }       p->next = np;    } } void print_graph(int n) { //in đồ thị    for (int i = 0; i < n; i++) {       cout << "Adjacency List of " << arr[i].v << ": ";       while (arr[i].ptr != NULL) {          cout << (arr[i].ptr)->des << " ";          arr[i].ptr = (arr[i].ptr)->next;       }       cout << endl;    } } //kiểm tra đồ thị có phải DAG hay không. int checkCG(int n) {    int cnt = 0;    int 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; }i nt 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