Yếu hoặc mạnh liên thông cho một đồ thị có hướng cho trước có thể tìm bằng DFS. Đây là chương trình C++ cho bài toán này.
Các hàm dùng
Begin Function fillorder() = điền stack với tất cả đỉnh. a) Đánh dấu nút hiện tại đã thăm và in ra b) Đệ quy cho tất cả đỉnh kề c) Tất cả đỉnh đạt được từ v đã xử lý xong, đẩy v vào Stack End Begin Function DFS() : a) Đánh dấu nút hiện tại đã thăm và in ra b) Đệ quy cho tất cả đỉnh kề End
Ví dụ
#include <iostream> #include <list> #include <stack> using namespace std; class G { int m; list<int> *adj; //khai báo hàm void fillOrder(int n, bool visited[], stack<int> &Stack); void DFS(int n, bool visited[]); public: G(int N); //constructor 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; // Đánh dấu nút hiện tại đã thăm và in ra cout << n << " "; list<int>::iterator i; //Đệ quy cho tất cả đỉnh kề 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); //thêm w vào danh sách v } void G::fillOrder(int v, bool visited[], stack<int> &Stack) { visited[v] = true; //Đánh dấu nút hiện tại đã thăm và in ra list<int>::iterator i; //Đệ quy cho tất cả đỉnh kề for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) fillOrder(*i, visited, Stack); Stack.push(v); } int G::print() { //in giải pháp 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(); //Tạo đồ thị đảo ngược for (int i = 0; i < m; i++)//Đánh dấu tất cả đỉnh chưa thăm visited[i] = false; int count = 0; //xử lý các đỉnh theo thứ tự Stack while (Stack.empty() == false) { int v = Stack.top(); Stack.pop(); //lấy đỉnh từ stack 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; }Kết quả
Following are strongly connected components in given graph 4 0 1 2 3 Graph is weakly connected.