Kiểm tra đồ thị có phải cây (Check if Graph is Tree)

Giới thiệu

Cho đồ thị vô hướng, kiểm tra có phải cây không. Cây không chứa chu trình. Cách khác: đồ thị liên thông và có V-1 cạnh.

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

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

Thuật toán

isCycle(u, visited, parent)

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ì
      nếu isCycle(v, visited, u) thì return true
    ngược lại nếu v ≠ parent thì return true  // tìm thấy chu trình
  done
  return false
End

isTree(graph)

Begin
  định nghĩa mảng visited, đánh dấu tất cả chưa thăm
  nếu isCycle(0, visited, null) thì return false
  nếu đồ thị không liên thông thì return false
  return true
End

Ví dụ (C++)

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

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

bool isCycle(int u, bool visited[], int parent) {
  visited[u] = true;
  for(int v = 0; v < NODE; v++) {
    if(graph[u][v]) {
      if(!visited[v]) {
        if(isCycle(v, visited, u)) return true;
      } else if(v != parent) return true;
    }
  }
  return false;
}

bool isTree() {
  bool *vis = new bool[NODE];
  for(int i = 0; i < NODE; i++) vis[i] = false;
  if(isCycle(0, vis, -1)) return false;
  for(int i = 0; i < NODE; i++) if(!vis[i]) return false;
  return true;
}

int main() {
  if(isTree()) cout << "The Graph is a Tree.";
  else cout << "The Graph is not a Tree.";
}

Kết quả đầu ra

The Graph is a Tree.