用C ++程序查找无向图的连接组件

使用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 strongly connected components
   in given graph \n";
   if (g.print() > 1) {
      cout << "图是弱连接。";
   } else {
      cout << "图已牢固连接。";
   }
   return 0;
}

输出结果

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