C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

グラフ内のすべての前方エッジを検索するC++プログラム


このセクションでは、グラフ内のすべての前縁を見つけるためのC++プログラムを検討します。

アルゴリズム

地形機能用

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.

#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();
}

出力

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

  1. グラフ内のスーパー頂点を見つけるためのC++プログラム

    n個の頂点を持つグラフが与えられたとします。頂点には1からnの番号が付けられ、配列edgesで指定されたエッジによって接続されます。各頂点には、配列valuesで指定された1からnまでの数値内のx値があります。ここで、グラフからスーパー頂点を見つける必要があります。頂点1からiへの最短経路にi番目の頂点と同じ「x」値を持つ頂点がない場合、頂点iは「スーパー頂点」と呼ばれます。この基準を満たすすべての頂点を印刷します。 したがって、入力がn =5のようである場合、値={1、2、2、1、3}、エッジ={{1、2}、{2、3}、{2、3}、{2、4 }、{4、5}}の場合、出力は1 345に

  2. 与えられたグラフのブリッジエッジの数を見つけるためのC++プログラム

    n個の頂点とm個のエッジを含む重み付けされていない無向グラフが与えられたとします。グラフのブリッジエッジは、グラフを削除するとグラフが切断されるエッジです。与えられたグラフでそのようなグラフの数を見つける必要があります。グラフには、平行なエッジや自己ループは含まれていません。 したがって、入力がn =5、m =6、edges ={{1、2}、{1、3}、{2、3}、{2、4}、{2、5}、{3 、5}}の場合、出力は1になります。 グラフには、{2、4}のブリッジエッジが1つだけ含まれています。 これを解決するには、次の手順に従います- mSize := 100 Define an