ตรวจสอบว่ากราฟเชื่อมต่ออย่างแน่นหนา - ชุดที่ 1 (Kosaraju โดยใช้ DFS) ใน C++

สมมุติว่าเรามีกราฟ เราต้องตรวจสอบว่ากราฟมีการเชื่อมต่ออย่างแน่นหนาหรือไม่โดยใช้อัลกอริธึม Kosaraju กราฟมีการเชื่อมต่อกันอย่างแน่นหนา หากมีจุดยอดสองจุดใดมีเส้นทางระหว่างกัน แสดงว่ากราฟนั้นเชื่อมต่อกัน กราฟที่ไม่มีทิศทางคือกราฟที่เชื่อมต่อกันอย่างแน่นหนา

กราฟที่ไม่ระบุทิศทางบางส่วนอาจเชื่อมต่อได้ แต่ไม่เชื่อมโยงอย่างแน่นหนา นี่คือตัวอย่างกราฟที่เชื่อมโยงกันอย่างมาก

นี่คือตัวอย่างกราฟที่เชื่อมต่อแต่ไม่เชื่อมโยงกันอย่างแน่นหนา

มาดูวิธีการตรวจสอบกราฟว่าเชื่อมกันอย่างแน่นหนาหรือไม่อย่างไร โดยใช้ขั้นตอนวิธีโกศราจุุดังต่อไปนี้

ขั้นตอน −

• ทำเครื่องหมายโหนดทั้งหมดว่าไม่ได้เยี่ยมชม

• เริ่มต้นการข้ามผ่าน DFS จากจุดยอดใดก็ได้ที่คุณกำหนดเอง หาก DFS ไม่สามารถเยี่ยมชมโหนดทั้งหมดได้ ให้คืนค่าเท็จ

• กลับขอบของกราฟทั้งหมด

• ตั้งค่าจุดยอดทั้งหมดเป็นโหนดที่ไม่ได้เยี่ยมชมอีก

• เริ่มการข้ามผ่าน 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