การปิดเกี่ยวข้องข้ามของกราฟ (Transitive Closure)

การปิดเกี่ยวข้องข้าม (Transitive Closure) คือเมทริกซ์การเข้าถึง (Reachability Matrix) ที่บอกว่า จากโหนด u สามารถไปถึงโหนด v ได้หรือไม่ สำหรับทุกคู่โหนด (u, v)

เมทริกซ์ผลลัพธ์เป็นแบบ Boolean: ค่า 1 หมายถึงมีเส้นทางอย่างน้อย 1 เส้นทางจาก u ไป v

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
1 1 0 1
0 1 1 0
0 0 1 1
0 0 0 1

Output: เมทริกซ์ Transitive Closure
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1

อัลกอริทึม

transClosure(graph) - ใช้หลักการ Floyd-Warshall แบบ Boolean

Begin
  คัดลอกเมทริกซ์ตyacency ไปเป็น transMat
  
  for ทุกโหนด k do
    for ทุกโหนด i do
      for ทุกโหนด j do
        transMat[i, j] := transMat[i, j] OR (transMat[i, k] AND transMat[k, j])
      done
    done
  done
  
  แสดง transMat
End

ตัวอย่างโค้ด (C++)

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

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];
  
  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++) {
    for(int j = 0; j < NODE; j++)
      cout << result[i][j] << " ";
    cout << endl;
  }
}

int main() {
  transClosure();
}

ผลลัพธ์