โปรแกรม C++ ตรวจสอบกราฟว่า Strongly Connected หรือไม่

กราฟที่เชื่อมต่ออย่างแข็งแกร่ง (Strongly Connected Graph)

ในกราฟมีทิศทาง (directed graph) องค์ประกอบ (components) ถูกกล่าวว่าเป็น strongly connected เมื่อมีเส้นทางระหว่างแต่ละคู่ของจุดยอดในองค์ประกอบหนึ่ง

เพื่อแก้อัลกอริทึมนี้ ขั้นแรก ใช้อัลกอริทึม DFS เพื่อหาเวลาสิ้นสุด (finish time) ของแต่ละจุดยอด ต่อมา หาเวลาสิ้นสุดของกราฟทรานสโพส (transposed graph) จากนั้น จุดยอดถูกจัดเรียงตามลำดับดังนิพจน์ (topological sort) แบบ descending

Input: เมทริกซ์ความติดกันของกราฟ

Output: Following are strongly connected components in given graph -

0 1 2 3 4

อัลกอริทึม

traverse(graph, start, visited)

Input: กราฟที่จะท่องไป, จุดยอดเริ่มต้น, และธงของโหนดที่เยี่ยมชมแล้ว

Output: ท่องทุกโหนดด้วยเทคนิค DFS และแสดงโหนด

เริ่มต้น
  ทำเครื่องหมาย start ว่าเยี่ยมชมแล้ว
  สำหรับทุกโหนด v ที่เชื่อมต่อกับ start
    ถ้า v ยังไม่ถูกเยี่ยมชม ให้ traverse(graph, v, visited)
สิ้นสุด

topoSort(u, visited, stack)

Input - โหนดเริ่มต้น, ธงสำหรับจุดยอดที่เยี่ยมชมแล้ว, สแต็ก

Output - เติมสแต็กขณะจัดเรียงกราฟ

เริ่มต้น
  ทำเครื่องหมาย u ว่าเยี่ยมชมแล้ว
  สำหรับทุกโหนด v ที่เชื่อมต่อกับ u
    ถ้า v ยังไม่ถูกเยี่ยมชม ให้ topoSort(v, visited, stack)
  ดัน u เข้าไปในสแต็ก
สิ้นสุด

getStrongConComponents(graph)

Input - กราฟที่กำหนด

Output - องค์ประกอบที่เชื่อมต่ออย่างแข็งแกร่งทั้งหมด

เริ่มต้น
  เริ่มต้นทุกโหนดเป็น unvisited
  สำหรับทุกโหนด i ในกราฟ
    ถ้า i ยังไม่ถูกเยี่ยมชม ให้ topoSort(i, vis, stack)
  ทำให้ทุกโหนดเป็น unvisited อีกครั้ง
  transGraph := ทรานสโพสของกราฟที่กำหนด
  while stack ไม่ว่าง
    ดึงโหนดจากสแต็กและเก็บใน v
    ถ้า v ยังไม่ถูกเยี่ยมชม ให้ traverse(transGraph, v, visited)
สิ้นสุด

โค้ดตัวอย่าง

#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() {
    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;
    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;
    for(int v = 0; v < NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u);
}

void getStrongConComponents() {
    stack<int> stk;
    bool vis[NODE];
    for(int i = 0; i < NODE; i++)
        vis[i] = false;
    for(int i = 0; i < NODE; i++)
        if(!vis[i])
            topoSort(i, vis, stk);
    for(int i = 0; i < NODE; i++)
        vis[i] = false;
    transpose();
    while(!stk.empty()) {
        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