डेप्थ फर्स्ट सर्च (DFS) एक एल्गोरिदम है जो एक ग्राफ को पार करता है और वापस आने से पहले सभी नोड्स को विजिट करता है जिसे यह निर्धारित कर सकता है। साथ ही, यह निर्धारित करता है कि दो नोड्स के बीच कोई पथ मौजूद है या नहीं।
यह ग्राफ या ट्री को गहराई-वार तरीके से खोजता है।
एल्गोरिदम
डेप्थ फर्स्ट सर्च (DFS) के कार्यान्वयन के लिए एक एल्गोरिदम नीचे दिया गया है:
चरण 1 - प्रारंभ में स्टैक खाली है।
चरण 2 - यदि विजिट किए जाने वाले नोड स्टैक में मौजूद नहीं है, तो हम इसे स्टैक पर पुश करते हैं और इसे विजिटेड के रूप में मार्क करते हैं।
चरण 3 - फिर, जांचें कि क्या वर्तमान नोड हमारे खोज मानदंड से मेल खाता है या नहीं।
चरण 3.1 - यदि यह है, तो हमारा काम हो गया।
चरण 4 - अन्यथा, हमें वर्तमान नोड से सभी आसन्न नोड्स पर जाने की आवश्यकता है।
चरण 4.1 - फिर उन प्रकार के सभी नोड्स को किसी भी क्रम में विजिट करें, और खोजते रहें।
चरण 5 - यदि सभी आसन्न नोड्स पहले से ही विजिटेड हैं तो यह एक डेड एंड बन जाता है।
चरण 6 - हम पहले से विजिटेड नोड पर जाते हैं और स्टैक से हालिया नोड को पॉप करते हैं।
चरण 7 - एल्गोरिदम समाप्त हो जाएगा यदि सभी नोड्स खोजे जा चुके हैं, या यदि हमें हमारा उत्तर मिल जाता है।
प्रोग्राम
निम्नलिखित C प्रोग्राम डेप्थ फर्स्ट सर्च (DFS) के कार्यान्वयन के लिए है:
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 void addVertex(char); void addEdge(int,int ); void displayVertex(int); void depthFirstSearch(); int getAdjUnvisitedVertex(int); struct Vertex { char label; bool visited; }; //स्टैक वेरिएबल्स int stack[MAX]; int top = -1; //ग्राफ वेरिएबल्स //वर्टेक्स की सरणी struct Vertex* lstVertices[MAX]; //एडजेंसी मैट्रिक्स int adjMatrix[MAX][MAX]; //वर्टेक्स काउंट int vertexCount = 0; //स्टैक फंक्शन्स void push(int item) { stack[++top] = item; } int pop() { return stack[top--]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //ग्राफ फंक्शन्स //वर्टेक्स लिस्ट में वर्टेक्स जोड़ें void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //एज सरणी में एज जोड़ें void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //वर्टेक्स प्रदर्शित करें void displayVertex(int vertexIndex) { printf("%c ",lstVertices[vertexIndex]->label); } //आसन्न अविजिटेड वर्टेक्स प्राप्त करें int getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; i < vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) { return i; } } return -1; } void depthFirstSearch() { int i; //पहले नोड को विजिटेड के रूप में मार्क करें lstVertices[0]->visited = true; //वर्टेक्स प्रदर्शित करें displayVertex(0); //स्टैक में वर्टेक्स इंडेक्स पुश करें push(0); while(!isStackEmpty()) { //स्टैक के शीर्ष पर मौजूद वर्टेक्स का अविजिटेड वर्टेक्स प्राप्त करें int unvisitedVertex = getAdjUnvisitedVertex(peek()); //कोई आसन्न वर्टेक्स नहीं मिला if(unvisitedVertex == -1) { pop(); } else { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); push(unvisitedVertex); } } //स्टैक खाली है, खोज पूरी, विजिटेड फ्लैग रीसेट करें for(i = 0;i < vertexCount;i++) { lstVertices[i]->visited = false; } } int main() { int i, j; for(i = 0; i < MAX; i++) // एडजेंसी सेट करें { for(j = 0; j < MAX; j++) // मैट्रिक्स को 0 पर adjMatrix[i][j] = 0; addVertex('S'); // 0 addVertex('A'); // 1 addVertex('B'); // 2 addVertex('C'); // 3 addVertex('D'); // 4 addEdge(0, 1); // S - A addEdge(0, 2); // S - B addEdge(0, 3); // S - C addEdge(1, 4); // A - D addEdge(2, 4); // B - D addEdge(3, 4); // C - D printf("Depth First Search: "); depthFirstSearch(); return 0; }आउटपुट
जब उपरोक्त प्रोग्राम निष्पादित होता है, तो यह निम्नलिखित परिणाम उत्पन्न करता है:
Depth First Search: S A D B C
