โปรแกรม C++ ตรวจสอบ Weakly Connected หรือ Strongly Connected สำหรับ Directed Graph

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

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

Begin
  Function fillorder() = เติม stack ด้วยโหนดทั้งหมด
    a) ทำเครื่องหมายโหนดปัจจุบัน visited และพิมพ์
    b) Recur สำหรับโหนดติดกันทั้งหมด
    c) โหนดที่เข้าถึงได้จาก v ประมวลผลเสร็จแล้ว push v เข้า Stack
End
Begin
  Function DFS():
    a) ทำเครื่องหมายโหนดปัจจุบัน visited และพิมพ์
    b) Recur สำหรับโหนดติดกันทั้งหมด
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] == false)
      fillOrder(i, visited, Stack);
  G graph = getTranspose();
  for (int i = 0; i < m; i++)
    visited[i] = false;
  int count = 0;
  while (Stack.empty() == false) {
    int v = Stack.top();
    Stack.pop();
    if (visited[v] == false) {
      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.