सी भाषा का उपयोग करते हुए डीएफएस का कार्यान्वयन

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

यह एक ग्राफ या पेड़ को गहराई से खोजता है।

एल्गोरिदम

गहराई पहली खोज (डीएफएस) के कार्यान्वयन के लिए नीचे दिया गया एल्गोरिदम है -

चरण 1 - शुरू में स्टैक खाली होता है।

चरण 2 - यदि विज़िट किया जाने वाला नोड स्टैक में मौजूद नहीं है, तो हम उसे स्टैक पर धकेलते हैं और विज़िट किए गए के रूप में चिह्नित करते हैं।

चरण 3 - फिर, जांचें कि वर्तमान नोड हमारे खोज मानदंड से मेल खाता है या नहीं।

चरण 3.1 - अगर यह वहां है, तो हम कर चुके हैं।

चरण 4 - अन्यथा, हमें वर्तमान नोड से सभी आसन्न नोड्स पर जाने की आवश्यकता है।

चरण 4.1 - फिर किसी भी क्रम में सभी प्रकार के नोड्स पर जाएं, और खोजते रहें।

चरण 5 - यदि सभी आसन्न नोड्स पहले ही देखे जा चुके हैं तो यह एक डेड एंड बन जाता है।

चरण 6 - हम पहले देखे गए नोड पर जाते हैं और स्टैक से हाल के नोड को पॉप करते हैं।

चरण 7 - यदि सभी नोड्स खोजे गए हैं, या यदि हमें अपना उत्तर मिल जाता है, तो एल्गोरिथम समाप्त हो जाएगा।

कार्यक्रम

गहराई प्रथम खोज (डीएफएस) के कार्यान्वयन के लिए सी कार्यक्रम निम्नलिखित है:-

#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;
};
//stack variables
int stack[MAX];
int top = -1;
//graph variables
//array of vertices
struct Vertex* lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
   stack[++top] = item;
}
int pop() {
   return stack[top--];
}
int peek() {
   return stack[top];
}
bool isStackEmpty() {
   return top == -1;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label) {
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
   vertex->label = label;
   vertex->visited = false;
   lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start,int end) {
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex) {
   printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
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;
   //mark first node as visited
   lstVertices[0]->visited = true;
   //display the vertex
   displayVertex(0);
   //push vertex index in stack
   push(0);
   while(!isStackEmpty()) {
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
      //no adjacent vertex found
      if(unvisitedVertex == -1) {
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }
   //stack is empty, search is complete, reset the visited flag
   for(i = 0;i < vertexCount;i++) {
      lstVertices[i]->visited = false;
   }
}
int main() {
   int i, j;
   for(i = 0; i < MAX; i++) // set adjacency {
      for(j = 0; j < MAX; j++) // matrix to 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