ग्राफ और इसके ट्रैवर्सल एल्गोरिदम

इस खंड में हम देखेंगे कि ग्राफ डेटा स्ट्रक्चर क्या है, और इसके ट्रैवर्सल एल्गोरिदम क्या हैं।

ग्राफ एक नॉन-लीनियर डेटा स्ट्रक्चर है। जिसमें कुछ नोड्स और उनके कनेक्टेड एज होते हैं। एज डायरेक्टेड या अनडायरेक्टेड हो सकते हैं। इस ग्राफ को G(V, E) के रूप में दर्शाया जा सकता है। निम्नलिखित ग्राफ को G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A)}) के रूप में दर्शाया जा सकता है।

ग्राफ में दो प्रकार के ट्रैवर्सल एल्गोरिदम होते हैं। इन्हें ब्रेडथ फर्स्ट सर्च और डेप्थ फर्स्ट सर्च कहा जाता है।

ब्रेडथ फर्स्ट सर्च (BFS)

ब्रेडथ फर्स्ट सर्च (BFS) ट्रैवर्सल एक एल्गोरिदम है, जिसका उपयोग दिए गए ग्राफ के सभी नोड्स को विजिट करने के लिए किया जाता है। इस ट्रैवर्सल एल्गोरिदम में एक नोड चुना जाता है और फिर सभी आसन्न नोड्स को एक-एक करके विजिट किया जाता है। सभी आसन्न वर्टेक्स पूरे होने के बाद, यह आगे बढ़कर दूसरे वर्टेक्स की जांच करता है और फिर से उसके आसन्न वर्टेक्स की जांच करता है।

एल्गोरिदम

bfs(vertices, start) इनपुट: वर्टेक्स की सूची, और प्रारंभिक वर्टेक्स। आउटपुट: सभी नोड्स को ट्रैवर्स करें, यदि ग्राफ कनेक्टेड है। Begin    एक खाली कतार que परिभाषित करें    सबसे पहले सभी नोड्स की स्थिति को अनविजिटेड के रूप में चिह्नित करें    प्रारंभिक वर्टेक्स को que में जोड़ें    while que खाली नहीं है, do       que से आइटम डिलीट करें और u पर सेट करें       वर्टेक्स u प्रदर्शित करें       u के साथ आसन्न सभी वर्टेक्स 1 के लिए, do          if vertices[i] अनविजिटेड है, then             vertices[i] को अस्थायी रूप से विजिटेड के रूप में चिह्नित करें             v को कतार में जोड़ें          चिह्नित करें       done       u को पूरी तरह से विजिटेड के रूप में चिह्नित करें    done End

डेप्थ फर्स्ट सर्च (DFS)

डेप्थ फर्स्ट सर्च (DFS) एक ग्राफ ट्रैवर्सल एल्गोरिदम है। इस एल्गोरिदम में एक प्रारंभिक वर्टेक्स दिया जाता है, और जब एक आसन्न वर्टेक्स मिलता है, तो यह पहले उस आसन्न वर्टेक्स पर जाता है और उसी तरीके से ट्रैवर्स करने का प्रयास करता है।

एल्गोरिदम

dfs(vertices, start) इनपुट: सभी वर्टेक्स की सूची, और प्रारंभिक नोड। आउटपुट: ग्राफ में सभी नोड्स को ट्रैवर्स करें। Begin    प्रारंभ में सभी नोड्स के लिए स्थिति को अनविजिटेड बनाएं    start को स्टैक में पुश करें    while स्टैक खाली नहीं है, do       स्टैक से एलिमेंट पॉप करें और u पर सेट करें       नोड u प्रदर्शित करें       if u विजिटेड नहीं है, then          u को विजिटेड के रूप में चिह्नित करें          u से जुड़े सभी नोड्स i के लिए, do             if ith वर्टेक्स अनविजिटेड है, then                ith वर्टेक्स को स्टैक में पुश करें                ith वर्टेक्स को विजिटेड के रूप में चिह्नित करें          done    done End