ग्राफ का संक्रामक समापन

संक्रामक समापन एक ग्राफ के शीर्ष u से शीर्ष v तक पहुंचने की पहुंच मैट्रिक्स है। एक ग्राफ दिया गया है, हमें एक शीर्ष v ढूंढना है जो किसी अन्य शीर्ष u से पहुंच योग्य है, सभी शीर्ष जोड़े (u, v) के लिए।

अंतिम मैट्रिक्स बूलियन प्रकार का है। जब शीर्ष u से शीर्ष v के लिए मान 1 होता है, तो इसका मतलब है कि u से v तक कम से कम एक पथ है।

इनपुट और आउटपुट

इनपुट: 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 आउटपुट: संक्रामक समापन का मैट्रिक्स 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1

एल्गोरिदम

transClosure(graph)

इनपुट: दिया गया ग्राफ।
आउटपुट: संक्रामक समापन मैट्रिक्स।

शुरू     आसन्नता मैट्रिक्स को transMat नामक दूसरी मैट्रिक्स में कॉपी करें     ग्राफ में किसी भी शीर्ष k के लिए, करें       ग्राफ में प्रत्येक शीर्ष i के लिए, करें         ग्राफ में प्रत्येक शीर्ष j के लिए, करें           transMat[i, j] := transMat[i, j] OR (transMat[i, k]) AND transMat[k, j])         किया       किया     किया     transMat प्रदर्शित करें अंत 

<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
आउटपुट
1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1