यदि एक डायरेक्टेड ग्राफ दिया गया है, तो दिए गए ग्राफ में सभी वर्टेक्स जोड़े (i, j) के लिए निर्धारित करें कि क्या वर्टेक्स j, वर्टेक्स i से पहुंच योग्य है। पहुंच योग्य का मतलब है कि वर्टेक्स i से j तक एक पाथ है। यह पहुंच मैट्रिक्स ग्राफ के ट्रांजिटिव क्लोजर कहलाता है। वार्शल एल्गोरिदम आमतौर पर दिए गए ग्राफ G के ट्रांजिटिव क्लोजर को खोजने के लिए उपयोग किया जाता है। यहां इस एल्गोरिदम को इम्प्लीमेंट करने का एक C++ प्रोग्राम है।
एल्गोरिदम
Begin 1. नोड्स की अधिकतम संख्या को इनपुट के रूप में लें। 2. नोड्स को a, b, c... के रूप में लेबल करें। 3. नोड्स के बीच कोई एज मौजूद है या नहीं, इसकी जांच करने के लिए फॉर लूप बनाएं: // a का ASCII कोड 97 है i = 97 से (97 + n_nodes)-1 तक j = 97 से (97 + n_nodes)-1 तक यदि एज मौजूद है तो करें, adj[i - 97][j - 97] = 1 अन्यथा adj[i - 97][j - 97] = 0 लूप समाप्त लूप समाप्त। 4. ग्राफ के ट्रांजिटिव क्लोजर को प्रिंट करने के लिए: i = 0 से n_nodes-1 तक c = 97 + i लूप समाप्त। i = 0 से n_nodes-1 तक c = 97 + i j = 0 से n_nodes-1 तक 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 << "\n\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
