グラフが強く接続されているかどうかを確認します-C++でセット1（DFSを使用するKosaraju）

グラフがあるとします。 Kosarajuアルゴリズムを使用して、グラフが強く接続されているかどうかを確認する必要があります。グラフは強く接続されていると言われ、2つの頂点の間にパスがある場合、グラフは接続されます。無向グラフは強く結びついたグラフです。

一部の無向グラフは接続されている可能性がありますが、強く接続されていない可能性があります。これは、強く接続されたグラフの例です。

これは、接続されているが強く接続されていないグラフの例です。

ここでは、コサラジュアルゴリズムの次の手順を使用して、グラフが強く関連しているかどうかを確認する方法を説明します。

手順 −

• すべてのノードを未訪問としてマークします

• 任意の頂点uからDFSトラバーサルを開始します。 DFSがすべてのノードにアクセスできない場合は、falseを返します。

• グラフのすべてのエッジを反転します

• すべての頂点を再度アクセスされていないノードとして設定します

• その頂点uからDFSトラバーサルを開始します。 DFSがすべてのノードへのアクセスに失敗した場合は、falseを返します。それ以外の場合はtrue。

例

#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
   int V;
   list<int> *adj;
   void dfs(int v, bool visited[]);
   public:
   Graph(int V) {
      this->V = V;
      adj = new list<int>[V];
   }
   ~Graph() {
      delete [] adj;
   }
   void addEdge(int v, int w);
   bool isStronglyConnected();
   Graph reverseArc();
};
void Graph::dfs(int v, bool visited[]) {
   visited[v] = true;
   list<int>::iterator i;
   for (i = adj[v].begin(); i != adj[v].end(); ++i)
   if (!visited[*i])
      dfs(*i, visited);
}
Graph Graph::reverseArc() {
   Graph graph(V);
   for (int v = 0; v < V; v++) {
      list<int>::iterator i;
      for(i = adj[v].begin(); i != adj[v].end(); ++i)
      graph.adj[*i].push_back(v);
   }
   return graph;
}
void Graph::addEdge(int u, int v) {
   adj[u].push_back(v);
}
bool Graph::isStronglyConnected() {
   bool visited[V];
   for (int i = 0; i < V; i++)
   visited[i] = false;
   dfs(0, visited);
   for (int i = 0; i < V; i++)
   if (visited[i] == false)
      return false;
   Graph graph = reverseArc();
   for(int i = 0; i < V; i++)
   visited[i] = false;
   graph.dfs(0, visited);
   for (int i = 0; i < V; i++)
   if (visited[i] == false)
      return false;
   return true;
}
int main() {
   Graph graph(5);
   graph.addEdge(0, 1);
   graph.addEdge(1, 2);
   graph.addEdge(2, 3);
   graph.addEdge(3, 0);
   graph.addEdge(2, 4);
   graph.addEdge(4, 2);
   graph.isStronglyConnected()? cout << "This is strongly connected" : cout << "This is not strongly connected";
}

出力

This is strongly connected