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

線形拡大を見つけることができるように、与えられた閉路グラフのエッジを削除する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<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) //to add reverse edge in the graph {
   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) // to add edge in the graph {
   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) //to print graph {
   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;
   }
}
//to check whether the graph is directed acyclic graph or not.
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;
}
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";
}

出力

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

  1. グラフから減らすことができるスコアの最大量を見つけるためのC++プログラム

    n個の頂点とm個のエッジを持つ重み付きの無向グラフがあるとします。グラフのスコアは、グラフ内のすべてのエッジの重みの加算として定義されます。エッジの重みは負の値になる可能性があり、それらを削除するとグラフのスコアが増加します。グラフを接続したまま、グラフからエッジを削除して、グラフのスコアを最小にする必要があります。減らすことができるスコアの最大量を見つける必要があります。 グラフは配列edgesで与えられ、各要素は{weight、{vertex1、vertex2}}の形式です。 したがって、入力がn =5、m =6、edges ={{2、{1、2}}、{2、{1、3}}、{1、{2、3}

  2. 特定のツリーグラフが線形であるかどうかをC++で確認します

    ここでは、ツリーグラフが線形であるかどうかを確認する方法を説明します。線形ツリーグラフは1行で表すことができます。これが線形ツリーグラフの例であると仮定します。 しかし、これは線形ではありません- グラフが線形であるかどうかを確認するには、2つの条件に従うことができます ノードの数が1の場合、ツリーグラフは線形です ノードの(n – 2)が次数2の場合 例 #include <iostream> #include <vector> #define N 4 using namespace std; class Graph{    p