C ++程序检查有向图是弱连接还是强连接

• Z时代
• 2024-01-10
• 分类：综合

可以使用DFS找出给定有向图的弱连接或强连接。这是此问题的C ++程序。

使用的功能

Begin
   Function fillorder() = fill stack with all the vertices.
   a) Mark the current node as visited and print it
   b) 为与该顶点相邻的所有顶点递归
   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) 为与该顶点相邻的所有顶点递归
End

示例

#include <iostream>
#include <list>
#include <stack>
using namespace std;
class G {
   int m;
   list<int> *adj;
   //功能声明
   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;
   //为与该顶点相邻的所有顶点递归
   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;
   //为与该顶点相邻的所有顶点递归
   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;
            //定义的顺序处理所有顶点
            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 spanly connected components in given graph \n";
   if (g.print() > 1) {
      cout << "图是弱连接。";
   } else {
      cout << "图已牢固连接。";
   }
   return 0;
}

输出结果

Following are spanly connected components in given graph
4
0 1 2 3
图是弱连接。

以上是 C ++程序检查有向图是弱连接还是强连接 的全部内容， 来源链接： utcz.com/z/316575.html