यदि एक डायरेक्टेड ग्राफ दिया गया है, तो दिए गए ग्राफ में सभी वर्टेक्स पेयर्स (i, j) के लिए यह निर्धारित करें कि वर्टेक्स j, वर्टेक्स i से पहुंच योग्य है या नहीं। पहुंच योग्य का अर्थ है कि वर्टेक्स i से j तक एक पथ मौजूद है। इस पहुंच-योग्यता मैट्रिक्स को ग्राफ के ट्रांजिटिव क्लोजर कहा जाता है। दिए गए ग्राफ G के ट्रांजिटिव क्लोजर को खोजने के लिए वार्शल एल्गोरिदम का आमतौर पर उपयोग किया जाता है। यहां इस एल्गोरिदम को लागू करने के लिए एक C++ प्रोग्राम है।
एल्गोरिदम
Begin 1.अधिकतम नोड्स की संख्या इनपुट के रूप में लें। 2.नोड्स को a, b, c ... के रूप में लेबल करें। 3.नोड्स के बीच कोई एज मौजूद है या नहीं, इसकी जांच करने के लिए एक फॉर लूप बनाएं: for i = 97 to less than 97 + number of nodes for j = 97 to less than 97 + number of nodes यदि एज मौजूद है तो करें, adj[i - 97][j - 97] = 1 अन्यथा adj[i - 97][j - 97] = 0 लूप समाप्त करें लूप समाप्त करें। 4.ग्राफ के ट्रांजिटिव क्लोजर को प्रिंट करने के लिए: for i = 0 to number of nodes c = 97 + i लूप समाप्त करें। for i = 0 to number of nodes c = 97 + i; for j = 0 to n_nodes print adj[I][j] लूप समाप्त करें लूप समाप्त करें End
उदाहरण कोड
#include<iostream> using namespace std; const int n_nodes = 20; int main() { int n_nodes, k, n; char i, j, res, c; int adj[10][10], path[10][10]; cout << "\n\tMaximum number of nodes in the graph :"; cin >>n; n_nodes = n; cout << "\nEnter 'y' for 'YES' and 'n' for 'NO' \n"; for (i = 97; i < 97 + n_nodes; i++) for (j = 97; j < 97 + n_nodes; j++) { cout << "\n\tIs there an edge from " << i << " to " << j << " ? "; cin >>res; if (res == 'y') adj[i - 97][j - 97] = 1; else adj[i - 97][j - 97] = 0; } cout << "\nTransitive Closure of the Graph:\n"; cout << "\n\t\t\t "; for (i = 0; i < n_nodes; i++) { c = 97 + i; cout << c << " "; } cout << "\n\n"; for (int i = 0; i < n_nodes; i++) { c = 97 + i; cout << "\t\t\t" << c << " "; for (int j = 0; j < n_nodes; j++) cout << adj[i][j] << " "; cout << "\n"; } return 0; }आउटपुट
Maximum number of nodes in the graph :4 Enter 'y' for 'YES' and 'n' for 'NO' Is there an edge from a to a ? y Is there an edge from a to b ?y Is there an edge from a to c ? n Is there an edge from a to d ? n Is there an edge from b to a ? y Is there an edge from b to b ? n Is there an edge from b to c ? y Is there an edge from b to d ? n Is there an edge from c to a ? y Is there an edge from c to b ? n Is there an edge from c to c ? n Is there an edge from c to d ? n Is there an edge from d to a ? y Is there an edge from d to b ? n Is there an edge from d to c ? y Is there an edge from d to d ? n Transitive Closure of the Graph: a b c d a 1 1 0 0 b 1 0 1 0 c 1 0 0 0 d 1 0 1 0
