โปรแกรม C++ หา Strongly Connected Components ในกราฟ

การหา Strongly Connected Components ในกราฟแบบมีทิศทาง

Weakly หรือ Strongly Connected ของกราฟแบบมีทิศทางสามารถหาได้ด้วย DFS นี่คือโปรแกรม C++ สำหรับปัญหานี้

ฟังก์ชันที่ใช้

Begin
    ฟังก์ชัน fillOrder() = เติม stack ด้วยจุดยอดทั้งหมด
    a) ทำเครื่องหมายโหนดปัจจุบันว่า visited และพิมพ์
    b) เรียกซ้ำสำหรับโหนดติดกันทั้งหมด
    c) จุดยอดที่เข้าถึงได้จาก v ถูกประมวลผลแล้ว push v เข้า Stack
End

Begin
    ฟังก์ชัน DFS():
    a) ทำเครื่องหมายโหนดปัจจุบันว่า visited และพิมพ์
    b) เรียกซ้ำสำหรับโหนดติดกันทั้งหมด
End

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

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class G {
    int m;
    list<int> *adj;
    void fillOrder(int n, bool visited[], stack<int> &Stack);
    void DFS(int n, bool visited[]);
public:
    G(int N);
    void addEd(int v, int w);
    int print();
    G getTranspose();
};

G::G(int m) {
    this->m = m;
    adj = new list<int>[m];
}

void G::DFS(int n, bool visited[]) {
    visited[n] = true;
    cout << n << " ";
    list<int>::iterator i;
    for (i = adj[n].begin(); i != adj[n].end(); ++i)
        if (!visited[*i]) DFS(*i, visited);
}

G G::getTranspose() {
    G g(m);
    for (int n = 0; n < m; n++) {
        list<int>::iterator i;
        for (i = adj[n].begin(); i != adj[n].end(); ++i)
            g.adj[*i].push_back(n);
    }
    return g;
}

void G::addEd(int v, int w) {
    adj[v].push_back(w);
}

void G::fillOrder(int v, bool visited[], stack<int> &Stack) {
    visited[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i]) fillOrder(*i, visited, Stack);
    Stack.push(v);
}

int G::print() {
    stack<int> Stack;
    bool *visited = new bool[m];
    for (int i = 0; i < m; i++) visited[i] = false;
    for (int i = 0; i < m; i++)
        if (!visited[i]) fillOrder(i, visited, Stack);
    G graph = getTranspose();
    for (int i = 0; i < m; i++) visited[i] = false;
    int count = 0;
    while (!Stack.empty()) {
        int v = Stack.top(); Stack.pop();
        if (!visited[v]) {
            graph.DFS(v, visited);
            cout << endl;
        }
        count++;
    }
    return count;
}

int main() {
    G g(5);
    g.addEd(2, 1);
    g.addEd(3, 2);
    g.addEd(1, 0);
    g.addEd(0, 3);
    g.addEd(3, 1);
    cout << "Following are strongly connected components in given graph \n";
    if (g.print() > 1) cout << "Graph is weakly connected.";
    else cout << "Graph is strongly connected.";
    return 0;
}

ผลลัพธ์

Following are strongly connected components in given graph
4
0 1 2 3
Graph is weakly connected.