Kiểm tra liên thông đồ thị có hướng

Giới thiệu

Kiểm tra đồ thị liên thông: duyệt từ mọi đỉnh, nếu sau duyệt vẫn còn đỉnh chưa thăm thì đồ thị không liên thông.

Với đồ thị có hướng, phải duyệt từ mọi đỉnh vì có thể có đỉnh chỉ có cạnh ra không có cạnh vào.

Dùng DFS đệ quy.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề:
0 1 0 0 0
0 0 1 0 0
0 0 0 1 1
1 0 0 0 0
0 1 0 0 0
Đầu ra: The Graph is connected.

Thuật toán

traverse(u, visited)

Begin
  đánh dấu u đã thăm
  với mọi đỉnh v kề u làm:
    nếu v chưa thăm thì traverse(v, visited)
  done
End

isConnected(graph)

Begin
  định nghĩa mảng visited
  với mọi đỉnh u trong đồ thị làm:
    đặt tất cả nút chưa thăm
    traverse(u, visited)
    nếu còn nút chưa thăm thì return false
  done
  return true
End

Ví dụ (C++)

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

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

void traverse(int u, bool visited[]) {
  visited[u] = true;
  for(int v = 0; v < NODE; v++) {
    if(graph[u][v] && !visited[v]) traverse(v, visited);
  }
}

bool isConnected() {
  bool *vis = new bool[NODE];
  for(int u = 0; u < NODE; u++) {
    for(int i = 0; i < NODE; i++) vis[i] = false;
    traverse(u, vis);
    for(int i = 0; i < NODE; i++) if(!vis[i]) return false;
  }
  return true;
}

int main() {
  if(isConnected()) cout << "The Graph is connected.";
  else cout << "The Graph is not connected.";
}

Kết quả đầu ra

The Graph is connected.