Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम ग्राफ़ में मज़बूती से जुड़े हुए घटकों को ढूँढ़ने के लिए

किसी दिए गए निर्देशित ग्राफ के लिए कमजोर या मजबूत रूप से जुड़ा हुआ डीएफएस का उपयोग करके पता लगाया जा सकता है। यह इस समस्या का C++ प्रोग्राम है।

प्रयुक्त कार्य

Begin
Function fillorder() = fill stack with all the vertices.
   a) Mark the current node as visited and print it
   b) Recur for all the vertices adjacent to this vertex
   c) All vertices reachable from v are processed by now, push v to Stack
End
Begin
Function DFS() :
   a) Mark the current node as visited and print it
   b) Recur for all the vertices adjacent to this vertex
End

उदाहरण

#include <iostream>
#include <list>
#include <stack>
using namespace std;
class G {
   int m;
   list<int> *adj;
   //declaration of functions
   void fillOrder(int n, bool visited[], stack<int> &Stack);
   void DFS(int n, bool visited[]);
   public:
   G(int N); //constructor
   void addEd(int v, int w);
   int print();
   G getTranspose();
};
G::G(int m) {
   this->m = m;
   adj = new list<int> [m];
}
void G::DFS(int n, bool visited[]) {
   visited[n] = true; // Mark the current node as visited and print it
   cout << n << " ";
   list<int>::iterator i;
   //Recur for all the vertices adjacent to this vertex
   for (i = adj[n].begin(); i != adj[n].end(); ++i)
      if (!visited[*i])
         DFS(*i, visited);
}
G G::getTranspose() {
   G g(m);
   for (int n = 0; n< m; n++) {
      list<int>::iterator i;
      for (i = adj[n].begin(); i != adj[n].end(); ++i) {
         g.adj[*i].push_back(n);
      }
   }
   return g;
}
void G::addEd(int v, int w) {
   adj[v].push_back(w); //add w to v's list
}
void G::fillOrder(int v, bool visited[], stack<int> &Stack) {
   visited[v] = true; //Mark the current node as visited and print it
   list<int>::iterator i;
   //Recur for all the vertices adjacent to this vertex
   for (i = adj[v].begin(); i != adj[v].end(); ++i)
      if (!visited[*i])
         fillOrder(*i, visited, Stack);
   Stack.push(v);
}
int G::print() { //print the solution
   stack<int> Stack;
   bool *visited = new bool[m];
   for (int i = 0; i < m; i++)
      visited[i] = false;
   for (int i = 0; i < m; i++)
      if (visited[i] == false)
         fillOrder(i, visited, Stack);
   G graph= getTranspose(); //Create a reversed graph
   for (int i = 0; i < m; i++)//Mark all the vertices as not visited
      visited[i] = false;
   int count = 0;
   //now process all vertices in order defined by Stack
   while (Stack.empty() == false) {
      int v = Stack.top();
      Stack.pop(); //pop vertex from stack
      if (visited[v] == false) {
         graph.DFS(v, visited);
         cout << endl;
      }
      count++;
   }
   return count;
}
int main() {
   G g(5);
   g.addEd(2, 1);
   g.addEd(3, 2);
   g.addEd(1, 0);
   g.addEd(0, 3);
   g.addEd(3, 1);
   cout << "Following are strongly connected components
   in given graph \n";
   if (g.print() > 1) {
      cout << "Graph is weakly connected.";
   } else {
      cout << "Graph is strongly connected.";
   }
   return 0;
}

आउटपुट

Following are strongly connected components in given
graph
4
0 1 2 3
Graph is weakly connected.

  1. सी++ प्रोग्राम एक अप्रत्यक्ष ग्राफ के कनेक्टेड घटकों को खोजने के लिए

    किसी दिए गए अप्रत्यक्ष ग्राफ के लिए कमजोर या मजबूत रूप से जुड़ा हुआ डीएफएस का उपयोग करके पता लगाया जा सकता है। यह इस समस्या का C++ प्रोग्राम है। प्रयुक्त कार्य Begin Function fillorder() = fill stack with all the vertices.    a) Mark the current node as visited and print it    b)

  1. सी ++ प्रोग्राम यह जांचने के लिए कि क्या यह कमजोर रूप से जुड़ा हुआ है या निर्देशित ग्राफ के लिए मजबूत रूप से जुड़ा हुआ है

    किसी दिए गए निर्देशित ग्राफ के लिए कमजोर या मजबूत रूप से जुड़ा हुआ डीएफएस का उपयोग करके पता लगाया जा सकता है। यह इस समस्या का C++ प्रोग्राम है। प्रयुक्त कार्य Begin    Function fillorder() = fill stack with all the vertices.    a) Mark the current node as visited and print it &nb

  1. C++ प्रोग्राम एक ग्राफ मैट्रिक्स के व्युत्क्रम को खोजने के लिए

    यह एक ग्राफ मैट्रिक्स के व्युत्क्रम को खोजने के लिए एक C++ प्रोग्राम है। मैट्रिक्स का व्युत्क्रम केवल तभी मौजूद होता है जब मैट्रिक्स गैर-एकवचन होता है, अर्थात, सारणिक 0 नहीं होना चाहिए। मैट्रिक्स का व्युत्क्रम कई तरीकों से पता लगाया जा सकता है। यहाँ हम आसन्न मैट्रिक्स और उसके सारणिक का उपयोग करके एक