Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình C ++ để kiểm tra xem nó được kết nối yếu hay kết nối mạnh cho một đồ thị được hướng dẫn

Kết nối yếu hoặc mạnh cho một đồ thị có hướng nhất định có thể được tìm hiểu bằng cách sử dụng DFS. Đây là một chương trình C ++ cho vấn đề này.

Các hàm được sử dụng

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

Ví dụ

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

Đầu ra

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