在图中查找良好反馈边集的 C++ 程序
在这个程序中，我们将基本上找到一个包含边的反馈弧集，当从图中删除时，图变成有向无环图。
算法
Begin
function checkCG(int n) :
n: number of vertices.
arr: struct graph variable.
Initialize cnt = 0 and size = (n-1).
For i =0 to n-1
if (cnt == size)
return 0
if (arr[i].ptr == NULL)
Increase 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示例
#include输出结果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) { //在图中添加反向边 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) { //在图中添加边 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) { //打印图形 for (int i = 0; i < n; i++) { cout << "邻接表 " << arr[i].v << ": "; while (arr[i].ptr != NULL) { cout << (arr[i].ptr)->des << " "; arr[i].ptr = (arr[i].ptr)->next; } cout << endl; } } //检查图是否为有向无环图。 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 << "顶点数： " << 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 << "反馈弧设置： "; if (checkCG(n) == 0) cout << " None"; }
顶点数： 5 邻接表 0: 1 邻接表 1: 2 邻接表 2: 1 3 0 邻接表 3: 邻接表 4: 2 反馈弧设置： None