Graph Traversal Techniques: Depth First Search (DFS) और Breadth First Search (BFS) Explained

Graphs एक महत्वपूर्ण data structure हैं, जो कि विभिन्न problem को solve करने में बहुत उपयोगी होती हैं। Graph traversal techniques का उपयोग करके हम graph में nodes या vertices को explore कर सकते हैं। traversal techniques हैं Depth First Search (DFS) और Breadth First Search (BFS)। आइए इन्हें समझते हैं।

Depth First Search (DFS)

Depth First Search (DFS) एक traversal technique है जो graph के गहरे हिस्सों की ओर तेजी से बढ़ता है। यह एक recursive approach का उपयोग करता है, जहाँ हम एक vertex से शुरू करते हैं और उसके सभी adjacent vertices को traverse करते हैं।

DFS की प्रक्रिया:

1. Start Node से traversal शुरू करें।

2. Current node को mark करें (visited)।

3. Current node के सभी unvisited adjacent nodes को explore करें।

4. जब कोई unvisited adjacent node नहीं हो, तो backtrack करें और दूसरे unvisited node को explore करें।

5. यह प्रक्रिया तब तक चलती है जब तक सभी nodes visit नहीं हो जाते।

DFS का Example:

मान लीजिए हमारे पास एक graph है:

A -- B

|       |

C -- D

DFS का traversal path हो सकता है: A → B → D → C

DFS के Advantages:

• Memory में कम space लेता है, खासकर जब graph sparse हो।

• यह graphs की topology को बेहतर तरीके से समझने में मदद करता है।

DFS के Disadvantages:

• Worst case में, यह बहुत लंबा हो सकता है, विशेष रूप से dense graphs में।

Breadth First Search (BFS)

Breadth First Search (BFS) एक और traversal technique है, जो nodes को level by level traverse करता है। BFS का उपयोग करके हम सबसे पहले starting node के सभी neighbors को visit करते हैं और फिर उनके neighbors को।

BFS की प्रक्रिया:

1. Start Node को queue में डालें।

2. जब तक queue empty न हो:

   1. Queue से एक node निकालें (current node)।

   2. Current node को mark करें (visited)।

   3. Current node के सभी unvisited adjacent nodes को queue में डालें।

BFS का Example:

उसी graph का उपयोग करते हुए:

A -- B

|       |

C -- D

BFS का traversal path हो सकता है: A → B → C → D

BFS के Advantages:

• Shortest path को खोजने में मदद करता है, खासकर unweighted graphs में।

• यह level order traversal के लिए आदर्श है।

BFS के Disadvantages:

• अधिक memory लेता है, क्योंकि यह सभी nodes को एक स्तर पर store करता है।

Conclusion 

DFS और BFS दोनों traversal techniques हैं, जो graph को traverse करने के लिए विभिन्न दृष्टिकोण प्रदान करती हैं। आपकी आवश्यकता और graph की प्रकृति के आधार पर, आप इनमें से किसी एक का चयन कर सकते हैं। जब आपको shortest path की आवश्यकता हो, तो BFS बेहतर विकल्प हो सकता है, जबकि DFS recursive problems को हल करने के लिए अधिक उपयुक्त है।