সি ভাষা ব্যবহার করে ডিএফএস বাস্তবায়ন

ডেপথ ফার্স্ট সার্চ (DFS) হল একটি অ্যালগরিদম যা একটি গ্রাফ অতিক্রম করে এবং ফিরে আসার আগে সমস্ত নোড পরিদর্শন করে তা নির্ধারণ করতে পারে। এছাড়াও, এটি নির্ধারণ করে যে দুটি নোডের মধ্যে একটি পথ বিদ্যমান কিনা।

এটি গভীরতা অনুসারে একটি গ্রাফ বা গাছ অনুসন্ধান করে৷

অ্যালগরিদম

গভীরতার প্রথম অনুসন্ধান (DFS) -

ধাপ 1 − প্রাথমিকভাবে স্ট্যাক খালি।

ধাপ 2 − যদি পরিদর্শন করার জন্য একটি নোড স্ট্যাকের মধ্যে উপস্থিত না থাকে, তাহলে আমরা এটিকে স্ট্যাকের উপর ঠেলে দিই এবং ভিজিট করা হিসাবে চিহ্নিত করি৷

ধাপ 3 − তারপর, বর্তমান নোডটি আমাদের অনুসন্ধানের মানদণ্ডের সাথে মেলে কিনা তা পরীক্ষা করে দেখুন৷

ধাপ 3.1৷ − যদি এটা থাকে, তাহলে আমাদের কাজ শেষ।

পদক্ষেপ 4৷ − অন্যথায়, আমাদের বর্তমান নোড থেকে সমস্ত সংলগ্ন নোডে যেতে হবে।

ধাপ 4.1৷ − তারপর যেকোন এলোমেলো ক্রমে এই সমস্ত ধরণের নোডগুলিতে যান এবং অনুসন্ধান চালিয়ে যান৷

ধাপ 5 − যদি সমস্ত সংলগ্ন নোড ইতিমধ্যেই পরিদর্শন করা হয় তবে এটি একটি মৃত প্রান্তে পরিণত হয়৷

ধাপ 6 − আমরা পূর্বে পরিদর্শন করা নোডে যাই এবং স্ট্যাক থেকে সাম্প্রতিক নোডটি পপ করি।

পদক্ষেপ 7 − সমস্ত নোড অনুসন্ধান করা হলে বা যদি আমরা আমাদের উত্তর পাই তাহলে অ্যালগরিদমটি বন্ধ হয়ে যাবে৷

প্রোগ্রাম

নিচে ডেপথ ফার্স্ট সার্চের (DFS) বাস্তবায়নের জন্য C প্রোগ্রাম রয়েছে −

#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