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

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

ในการแก้ปัญหาอัลกอริธึมนี้ ประการแรก อัลกอริทึม DFS ถูกใช้เพื่อรับเวลาสิ้นสุดของแต่ละจุดยอด ตอนนี้ให้หาเวลาสิ้นสุดของกราฟทรานสโพส จากนั้นจุดยอดจะถูกจัดเรียงตามลำดับจากมากไปน้อยตามการจัดเรียงทอพอโลยี

อินพุตและเอาต์พุต

Input:
Adjacency matrix of the graph.
0 0 1 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 0

Output:
Following are strongly connected components in given graph:
0 1 2
3
4

อัลกอริทึม

สำรวจ (กราฟ เริ่ม เข้าชม)

อินพุต: กราฟที่จะข้าม จุดยอดเริ่มต้น และแฟล็กของโหนดที่เข้าชม

ผลลัพธ์: ผ่านแต่ละโหนดในเทคนิค DFS และแสดงโหนด

Begin
   mark start as visited
   for all vertices v connected with start, do
      if v is not visited, then
         traverse(graph, v, visited)
   done
End

topoSort(u, เยี่ยมชม, stack)

ป้อนข้อมูล - โหนดเริ่มต้น ตั้งค่าสถานะสำหรับจุดยอดที่เข้าชม สแต็ก

ผลลัพธ์ − เติมสแตกขณะจัดเรียงกราฟ

Begin
   mark u as visited
   for all node v, connected with u, do
      if v is not visited, then
         topoSort(v, visited, stack)
   done
   push u into the stack
End

getStrongConComponents(กราฟ)

ป้อนข้อมูล: กราฟที่กำหนด

ผลลัพธ์ − ส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาทั้งหมด

Begin
   initially all nodes are unvisited
   for all vertex i in the graph, do
      if i is not visited, then
         topoSort(i, vis, stack)
   done

   make all nodes unvisited again
   transGraph := transpose of given graph

   while stack is not empty, do
      pop node from stack and take into v
      if v is not visited, then
         traverse(transGraph, v, visited)
   done
End

ตัวอย่าง

#include <iostream>
#include <stack>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {0, 0, 1, 1, 0},
   {1, 0, 0, 0, 0},
   {0, 1, 0, 0, 0},
   {0, 0, 0, 0, 1},
   {0, 0, 0, 0, 0}
};
                               
int transGraph[NODE][NODE];

void transpose() {    //transpose the graph and store to transGraph
   for(int i = 0; i<NODE; i++)
      for(int j = 0; j<NODE; j++)
         transGraph[i][j] = graph[j][i];
}    
         
void traverse(int g[NODE][NODE], int u, bool visited[]) {
   visited[u] = true;    //mark v as visited
   cout << u << " ";

   for(int v = 0; v<NODE; v++) {
      if(g[u][v]) {
         if(!visited[v])
            traverse(g, v, visited);
      }
   }
}  
                                               
void topoSort(int u, bool visited[], stack<int>&stk) {
   visited[u] = true;    //set as the node v is visited

   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]) {    //for allvertices v adjacent to u
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }

   stk.push(u);    //push starting vertex into the stack
}

void getStrongConComponents() {
   stack<int> stk;
   bool vis[NODE];

   for(int i = 0; i<NODE; i++)
      vis[i] = false;    //initially all nodes are unvisited
   
   for(int i = 0; i<NODE; i++)
      if(!vis[i])    //when node is not visited
         topoSort(i, vis, stk);
   
   for(int i = 0; i<NODE; i++)
      vis[i] = false;    //make all nodes are unvisited for traversal  
   transpose();    //make reversed graph
   
   while(!stk.empty()) {    //when stack contains element, process in topological order
      int v = stk.top(); stk.pop();
      if(!vis[v]) {
         traverse(transGraph, v, vis);
         cout << endl;
      }
   }
}

int main() {
   cout << "Following are strongly connected components in given graph: "<<endl;
   getStrongConComponents();
}

ผลลัพธ์

Following are strongly connected components in given graph:
0 1 2
3
4