Transitive Closure 그래프의 꼭짓점 u에서 꼭짓점 v까지 도달하는 도달 가능성 매트릭스입니다. 하나의 그래프가 주어지면 모든 정점 쌍(u, v)에 대해 다른 정점 u에서 도달할 수 있는 정점 v를 찾아야 합니다.
마지막 행렬은 부울 유형입니다. 꼭짓점 u에서 꼭짓점 v까지의 값이 1이면 u에서 v까지의 경로가 하나 이상 있음을 의미합니다.
입력 및 출력
Input: 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 Output: The matrix of transitive closure 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1
알고리즘
transColsure(graph)
입력: 주어진 그래프.
출력: 전이적 폐쇄 매트릭스.
Begin copy the adjacency matrix into another matrix named transMat for any vertex k in the graph, do for each vertex i in the graph, do for each vertex j in the graph, do transMat[i, j] := transMat[i, j] OR (transMat[i, k]) AND transMat[k, j]) done done done Display the transMat End
<2>예
#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]; //initially copy the graph to the result matrix 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++) { //print the result matrix for(int j = 0; j<NODE; j++) cout << result[i][j] << " "; cout << endl; } } int main() { transClosure(); }
출력
1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1