दृढ़ता से जुड़ा ग्राफ
एक निर्देशित ग्राफ दृढ़ता से जुड़ा है यदि किन्हीं दो शीर्षों के बीच दोनों दिशाओं में पथ मौजूद हो।
कोसराजू एल्गोरिदम (DFS आधारित)
- सभी नोड्स को अनविजिटेड मार्क करें
- किसी भी शीर्ष से DFS करें। यदि सभी नोड्स विजिट नहीं हुए → false
- सभी एज उलट दें (ट्रांसपोज ग्राफ)
- फिर से सभी अनविजिटेड मार्क करें
- उसी शीर्ष से DFS करें। यदि सभी विजिट नहीं हुए → false
- अन्यथा → true
उदाहरण कोड
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V;
list* adj;
void dfs(int v, bool visited[]);
public:
Graph(int V) { this->V = V; adj = new list[V]; }
~Graph() { delete[] adj; }
void addEdge(int v, int w) { adj[v].push_back(w); }
bool isStronglyConnected();
Graph reverseArc();
};
void Graph::dfs(int v, bool visited[]) {
visited[v] = true;
for (int u : adj[v])
if (!visited[u]) dfs(u, visited);
}
Graph Graph::reverseArc() {
Graph g(V);
for (int v = 0; v < V; v++)
for (int u : adj[v])
g.adj[u].push_back(v);
return g;
}
bool Graph::isStronglyConnected() {
bool visited[V];
fill(visited, visited+V, false);
dfs(0, visited);
for (int i = 0; i < V; i++) if (!visited[i]) return false;
Graph gr = reverseArc();
fill(visited, visited+V, false);
gr.dfs(0, visited);
for (int i = 0; i < V; i++) if (!visited[i]) return false;
return true;
}
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 0);
g.addEdge(2, 4);
g.addEdge(4, 2);
g.isStronglyConnected() ? cout << "This is strongly connected"
: cout << "This is not strongly connected";
return 0;
}
आउटपुट
This is strongly connected