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

グラフのエッジ接続を見つけるためのC++プログラム


このプログラムでは、グラフのエッジ接続を見つける必要があります。グラフのグラフのエッジ接続は、それがブリッジであることを意味し、グラフを削除すると切断されます。接続されたコンポーネントの数は、切断された無向グラフのブリッジを削除すると増加します。

関数と擬似コード:

Begin
   Function connections() is a recursive function to find out the connections:
   A) Mark the current node un visited.
   B) Initialize time and low value
   C) Go through all vertices adjacent to this
   D) Check if the subtree rooted with x has a connection to one of the ancestors of w. If the lowest vertex reachable from subtree under x is below u in DFS tree, then w-x has a connection.
   E) Update low value of w for parent function calls.
End
Begin
   Function Con() that uses connections():
   A) Mark all the vertices as unvisited.
   B) Initialize par and visited, and connections.
   C) Print the connections between the edges in the graph.
End

#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
   //declaration of functions
   int n;
   list<int> *adj;
   void connections(int n, bool visited[], int disc[], int low[],
   int par[]);
   public:
      G(int n); //constructor
      void addEd(int w, int x);
      void Con();
};
G::G(int n) {
   this->n = n;
   adj = new list<int> [n];
}
//add edges to the graph
void G::addEd(int w, int x) {
   adj[x].push_back(w); //add u to v's list
   adj[w].push_back(x); //add v to u's list
}
void G::connections(int w, bool visited[], int dis[], int low[], int par[]) {
   static int t = 0;
   //mark current node as visited
   visited[w] = true;
   dis[w] = low[w] = ++t;
   //Go through all adjacent vertices
   list<int>::iterator i;
   for (i = adj[w].begin(); i != adj[w].end(); ++i) {
      int x = *i; //x is current adjacent
      if (!visited[x]) {
         par[x] = w;
         connections(x, visited, dis, low, par);
         low[w] = min(low[w], low[x]);
         // If the lowest vertex reachable from subtree under x is below w in DFS tree, then w-x is a connection
         if (low[x] > dis[w])
            cout << w << " " << x << endl;
      } else if (x != par[w])
         low[w] = min(low[w], dis[x]);
   }
}
void G::Con() {
   // Mark all the vertices as unvisited
   bool *visited = new bool[n];
   int *dis = new int[n];
   int *low = new int[n];
   int *par = new int[n];
   for (int i = 0; i < n; i++) {
      par[i] = N;
      visited[i] = false;
   }
   //call the function connections() to find edge connections
   for (int i = 0; i < n; i++)
      if (visited[i] == false)
         connections(i, visited, dis, low, par);
}
int main() {
   cout << "\nConnections in first graph \n";
   G g1(5);
   g1.addEd(1, 2);
   g1.addEd(3, 2);
   g1.addEd(2, 1);
   g1.addEd(0, 1);
   g1.addEd(1, 4);
   g1.Con();
   return 0;
}

出力

Connections in first graph
2 3
1 2
1 4
0 1

  1. 与えられたグラフのブリッジエッジの数を見つけるための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

  2. グラフのエッジカバーを計算するC++プログラム

    グラフの頂点の数がnの場合、タスクはグラフのエッジカバーを計算することです。エッジカバーは、グラフのすべての頂点をカバーするために必要なエッジの最小数を見つけることです。 n=5のように その場合、そのグラフは次のようになります- したがって、そのエッジカバーは3 nが8である別の例を見てみましょう そして、そのエッジカバーは次のようになります:4 例 Input: n= 5 Output: 3 Input: n= 8 Output: 4 以下で使用されるアプローチは次のとおりです − ユーザーからの入力を受け取ります 頂点の数の結果の上限値を2.0