Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> 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 शीर्ष हैं। कोने 1 से n तक गिने जाते हैं, और वे सरणी किनारों में दिए गए किनारों से जुड़े होते हैं। प्रत्येक शीर्ष का 1 से n तक की संख्या के भीतर x मान होता है जो कि सरणी मान में दिया जाता है। अब, हमें ग्राफ से अति शीर्षों का पता लगाना है। एक शीर्ष i को सु

  1. C++ प्रोग्राम दिए गए ग्राफ़ में ब्रिज किनारों की संख्या का पता लगाने के लिए

    मान लीजिए, हमें एक अभारित, अप्रत्यक्ष ग्राफ दिया गया है जिसमें n कोने और m किनारे हैं। ग्राफ़ में ब्रिज का किनारा वह किनारा होता है जिसके हटाने से ग्राफ़ डिस्कनेक्ट हो जाता है। हमें दिए गए आलेख में ऐसे आलेखों की संख्या ज्ञात करनी है। ग्राफ़ में समानांतर किनारे या सेल्फ़-लूप नहीं होते हैं। इसलिए, यद

  1. C++ प्रोग्राम ग्राफ के एज कवर की गणना करने के लिए

    ग्राफ़ के शीर्षों की संख्या को देखते हुए, कार्य ग्राफ़ के किनारे कवर की गणना करना है। एज कवर ग्राफ़ के प्रत्येक शीर्ष को कवर करने के लिए आवश्यक किनारों की न्यूनतम संख्या ज्ञात करना है। जैसे हमारे पास n =5 . है तो इसका ग्राफ इस तरह होगा - तो इसका किनारा कवर 3 . है आइए एक और उदाहरण लेते हैं जह