Chương trình C ++ để tìm tất cả các cạnh chuyển tiếp trong một đồ thị

Trong phần này, chúng ta sẽ xem xét một chương trình C ++ để tìm tất cả các cạnh chuyển tiếp trong một đồ thị.

Thuật toán

Đối với hàm topo

Begin
   Declare function topo()
      Declare pointer v, m[][5] and i of the integer datatype.
      x = new Node_Inf.
      x->n = i.
      x->S_Time = c.
      Call function Push_Node(x).
      v[i] = 1.
      for (int j = 0; j < 5; j++)
         if (m[i][j] == 0) then
            continue;
         else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) then
         if (x->S_Time < srch_Node(j)) then
            Print "Forward Edge is between ".
            Print the values of forward edges.
            continue;
      else if (m[i][j] == 1 && v[j] == 0) then
         c++;
      Print "Forward Edge is between "
      Print the values of forward edges.
      Call topo(v,m,j) function.
      c++.
      x = pop()
      x->L_Time = c.
      Call Store_Node(x) function to store values into nodes.
   Return.
End.

Ví dụ

#include<iostream>
#include<conio.h>
using namespace std;
struct Node_Inf {
   int n;
   int L_Time, S_Time;
}
*x = NULL, *y = NULL;
struct Node_1 {
   Node_Inf *ptn;
   Node_1 *nxt;
}
*tp = NULL, *p = NULL, *npr = NULL;
struct Node_2 {
   Node_2 *lnk;
   Node_Inf *ptn1;

}
*hd = NULL, *m = NULL, *n = NULL, *npr1 = NULL;
int c = 0;
void Push_Node(Node_Inf *ptr) {
   npr = new Node_1;
   npr->ptn = ptr;
   npr->nxt = NULL;
   if (tp == NULL) {
      tp = npr;
   } else {
      npr->nxt = tp;
      tp = npr;
   }
}
Node_Inf *pop() {
   if (tp == NULL) {
      cout<<"underflow\n";
   } else {
      p = tp;
      tp = tp->nxt;
      return(p->ptn);
      delete(p);
   }
}
void Store_Node(Node_Inf *ptr1) {
   npr1 = new Node_2;
   npr1->ptn1 = ptr1;
   npr1->lnk = NULL;
   if (c == 0) {
      hd = npr1;
      m = hd;
      m->lnk = NULL;
      c++;
   } else {
      m = hd;
      npr1->lnk = m;
      hd = npr1;
   }
}
int srch_Node(int j) {
   Node_2 *t = hd;
   while (t != NULL) {
      if ((t->ptn1)->n == j)
      {
         break;
      } else {
         t = t->lnk;
         continue;
      }
   }
   return (t->ptn1)->L_Time;
}
int Exist_in_Stack(int j) {
   int flag = 0;
   p = tp;
   while (p != NULL) {
      if ((p->ptn)->n == j) {
         flag = 1;
         return flag;
      }
      p = p->nxt;
   }
   return flag;
}
void topo(int *v, int m[][5], int i) {
   x = new Node_Inf;
   x->n = i;
   x->S_Time = c;
   Push_Node(x);
   v[i] = 1;
   for (int j = 0; j < 5; j++) {
      if (m[i][j] == 0)
         continue;
      else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) {
         if (x->S_Time < srch_Node(j)) {
            cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
         }
         continue;
      } else if (m[i][j] == 1 && v[j] == 0) {
         c++;
         cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
         topo(v,m,j);
      }
   }
   c++;
   x = pop();
   x->L_Time = c;
   Store_Node(x);
   return;
}
int main() {
   int v[5],m[5][5];
   for (int i = 0; i < 5; i++)
   v[i] = 0;
   for (int i = 0; i < 5; i++) {
      cout<<" Enter the values of matrix::"<<i + 1<<endl;
      for(int j = 0; j < 5; j++) {
         cin>>m[i][j];
      }
   }
   topo(v,m,0);
   getch();
}

Đầu ra

Enter the values of matrix:1
0
1
0
1
0
Enter the values of matrix:2
1
0
0
1
0
Enter the values of matrix:3
1
0
0
0
1
Enter the values of matrix:4
0
1
1
0
0
Enter the values of matrix:5
1
1
0
0
0

Forward Edge is between 0 and 1

Forward Edge is between 1 and 3

Forward Edge is between 3 and 2

Forward Edge is between 2 and 4

Forward Edge is between 0 and 3