Bao truyền递 của đồ thị (Transitive Closure)

Bao truyền thích (Transitive Closure) là ma trận khả năng đạt được để đi từ đỉnh u đến đỉnh v của một đồ thị. Cho một đồ thị, ta phải tìm đỉnh v có thể đạt được từ đỉnh u khác, cho tất cả các cặp đỉnh (u, v).

Ma trận cuối cùng là kiểu Boolean. Khi có giá trị 1 cho đỉnh u đến đỉnh v, có nghĩa là tồn tại ít nhất một đường đi từ u đến v.

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

Đầu vào:
1 1 0 1
0 1 1 0
0 0 1 1
0 0 0 1
Đầu ra: Ma trận bao truyền thích
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1

Thuật toán

transClosure(graph)
Đầu vào: Đồ thị cho trước.
Đầu ra: Ma trận bao truyền thích.
Bắt đầu
  sao chép ma trận kề vào ma trận khác tên transMat
  với mọi đỉnh k trong đồ thị, thực hiện
    với mỗi đỉnh i trong đồ thị, thực hiện
      với mỗi đỉnh j trong đồ thị, thực hiện
        transMat[i, j] := transMat[i, j] OR (transMat[i, k] AND transMat[k, j])
      kết thúc
    kết thúc
  kết thúc
  Hiển thị transMat
Kết thúc

Ví dụ (C++)

#include <iostream>
#include <vector>
#define NODE 4
using namespace std;

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

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

int result[NODE][NODE];

void transClosure() {
  for(int i = 0; i < NODE; i++)
    for(int j = 0; j < NODE; j++)
      result[i][j] = graph[i][j]; // ban đầu sao chép đồ thị vào ma trận kết quả
  
  for(int k = 0; k < NODE; k++)
    for(int i = 0; i < NODE; i++)
      for(int j = 0; j < NODE; j++)
        result[i][j] = result[i][j] || (result[i][k] && result[k][j]);
  
  for(int i = 0; i < NODE; i++) {
    // in ma trận kết quả
    for(int j = 0; j < NODE; j++)
      cout << result[i][j] << " ";
    cout << endl;
  }
}

int main() {
  transClosure();
}

Đầu ra