मान लीजिए हमारे पास एक ग्राफ है। हमें यह जांचना है कि ग्राफ मजबूती से जुड़ा हुआ है या नहीं कोसरजू एल्गोरिथम का उपयोग कर रहा है। एक ग्राफ को दृढ़ता से जुड़ा हुआ कहा जाता है, यदि किन्हीं दो शीर्षों के बीच पथ है, तो ग्राफ जुड़ा हुआ है। एक अप्रत्यक्ष ग्राफ़ दृढ़ता से जुड़ा हुआ ग्राफ़ होता है।
कुछ अप्रत्यक्ष ग्राफ जुड़े हो सकते हैं लेकिन दृढ़ता से जुड़े नहीं। यह दृढ़ता से जुड़े ग्राफ़ का एक उदाहरण है।
यह कनेक्टेड का एक उदाहरण है, लेकिन दृढ़ता से कनेक्टेड ग्राफ़ नहीं है।
यहां हम देखेंगे कि कोसाराजू एल्गोरिथम के निम्नलिखित चरणों का उपयोग करके ग्राफ़ की जांच कैसे करें कि यह दृढ़ता से जुड़ा हुआ है या नहीं।
कदम -
-
सभी नोड्स को नहीं देखा के रूप में चिह्नित करें
-
किसी मनमाना शीर्ष u से DFS ट्रैवर्सल प्रारंभ करें। यदि डीएफएस सभी नोड्स पर जाने में विफल रहता है, तो झूठी वापसी करें।
-
ग्राफ़ के सभी किनारों को उलट दें
-
सभी शीर्षों को फिर से न देखे गए नोड्स के रूप में सेट करें
-
उस शीर्ष u से DFS ट्रैवर्सल प्रारंभ करें। यदि डीएफएस सभी नोड्स पर जाने में विफल रहता है, तो झूठी वापसी करें। अन्यथा सत्य।
उदाहरण
#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