Hello दोस्तों! आज मैं आपको इस पोस्ट में Graph Traversal in Data Structure in Hindi के बारें में बताऊंगा, और इसके example को भी पढेंगे, तो चलिए शुरू करते हैं:-
What is Graph Traversal
Graph Traversal का अर्थ है – graph की प्रत्येक node को visit करना ।
एक graph की vertices को visit करने के अनेक तरीके हो सकते है
जो दो तरीके हम आपको बताने जा रहे है
वो भूत ही प्रचुर मात्रा मे प्रयोग किए जाते है
और ये तरीके traversal के अत्यंत सरल तरीके सिद्ध हुये है
ये निम्नलिखित है ।
types of Graph Traversal
(1) Breadth First Search (BFS)
(2) Depth First Search (DFS)
BFS(Breadth First Search)in Hindi:-
जैसा की नाम से प्रतीत होता है की इस तरीके मे nodes को चौड़ाई से visit करना है ।
BFS मे पहले हम start vertex की समस्त vertices को visit करते है
और फिर इनकी सभी unvisited vertex को visit करते है ।
इसी प्रकार आगे तक समस्त vertices को visit किया जाता है ।
BFS के लिए निम्नलिखित algorithm को ध्यान मे रखते है –
status 1 = ready
status 2 = waiting
status 3 = process
Step1- graph की सभी node को visit के लिए तैयार रखे । (Status 1)
Step2- start vertex A को Queue मे डालकर इसका status waiting करे । (Status 2)
Step3- step 4 से step5 तक दोहराये जब तक queue खाली न हो जाये।
Step4- queue की पहली node n को queue से remove करके n को process कर दें । (Status 3)
Step5- queue के अंत मे n के सभी adjacent vertices जो की ready – state मे है को डाल दें । (Status 1)
Step 6- step3 का loop खत्म हुआ।
Step7- Exit
इस पूरे process को समझने के लिए न्निचे दिये गए उदाहरण का अध्ययन करे ।
इस चित्र के लिए पहले adjacent table बना लेते है –
अब हम किसी भी vertex को start vertex बनाकर कार्य शुरू कर सकते है
इस उदाहरण मे हमने B को start vertex माना है । अब हमे इसे queue मे डालना है ।
इस queue के दो भाग है – पहला भाग तो साधारण queue हिय जिसमे हम vertex की adjacent vertices डालेंगे ,
जबकि दूसरे भाग मे यह entry की गई है की वे किसकी adjacent vertices है जो जो vertices को queue मे डालना है ।
अब इन vertices की unvisited adjacent vertices को visit करना है
जैसे की हम C की बची adjacent verticesको queue मे डालेंगे ।
अब हमे D की बची adjacent vertices को भी queue मे डालना है ।
अब जैसे की हम देख सकते है की graph की समस्त nodes visit हो चुकी है ।
अतः graph का traversal सम्पन्न हो चुका है
और queue के नीचे लिखी list ही दिये गए graph का BFS है ।
एक graph BFS भिन्न हो सकता है । चूंकि यह start vertex पर निर्भर करता है
DFS(Depth First Search) in Hindi:-
इसके नाम से ही प्रतीत हो रहा है की यह तरीका graph को गहराई से visit करता है ।
DFS मे हम सबसे पहले start vertex को stack के द्वारा visit करते है
फिर इसकी समस्त adjacent vertices को stack मे डालकर stack के top पर स्थित क्रिया तब तक दोहराते है
जब तक की stack खाली न हो जाए ।
DFS करने के लिए अग्रलिखित algorithm को ध्यान मे रखते है
status 1 = ready
status 2 = waiting
status 3 = process
step1 graph की सभी node को visit के लिए तैयार रखे । (Status 1)
step2 start vertex को stack मे डालकर इसका status waiting कर दे । (Status 2)
step3 step 3 से 5 तब तक दोहराए जब तक की stack खाली न हो जाए.
step4 steck के top मे से node को निकालकर उसे process करे. (Status 3)
step5 n की adjacent vertices को stack मे डालकर उनका status 1 से 2 करे.
step6 step3 का loop खत्म हुआ ।
step7 exit.
इस पूरे process को समझने के लिए नीचे दिये गए उदाहरण का अध्ययन करे
अब start vertex को stack मे डाल दे
अब सबसे पहले visited node को stack के नीचे लिख ले ।
visited node की समस्त adjacent node को stack मे डाल दे।
अब पुनः top of the stack को stack से बाहर निकालकर इसकी adjacent को stack मे डाल दें
और इसी प्रकार तक आगे करते रहिए जब तक stack खाली न हो जाए
अब जैसे की हम देख सकते है की stack पूरा खाली हो चुका है अतः DFS सम्पन्न हो चुका है
खाली stack के नीचे list ही graph का DSF है
एक graph DSF भी भिन्न हो सकता है चूंकि यह भी start vertex पर निर्भर करता है
निवेदन:- अगर आपके लिए यह आर्टिकल useful रहा हो तो इसे अपने दोस्तों और classmates के साथ अवश्य share कीजिये, और या अन्य विषयों से related कोई question हो तो नीचे कमेंट के द्वारा बताइए. thanks.