ডেপথ ফার্স্ট সার্চ (DFS) একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা স্ট্যাক ব্যবহার করে গভীরা-প্রথমে নোড ভিজিট করে। পাথ আছে কিনা চেক করতেও ব্যবহৃত হয়।
অ্যালগরিদম
- স্ট্যাক খালি রাখুন।
- শুরু নোডকে স্টാക്കে পুশ করুন এবং ভিজিটেড মার্ক করুন।
- স্ট্যাক খালি না হওয়া পর্যন্ত:
- টপ নোডের অনভিজিটেড সন্নিহিত নোড খুঁজুন।
- পাওয়া গেলে সেটিকে ভিজিটেড করুন, ডিসপ্লে করুন, পুশ করুন।
- না পেলে পপ করুন (ব্যাকট্র্যাক)।
- সব নোড ভিজিট হলে বা টার্গেট পাওয়া গেলে থামুন।
C কোড (স্ট্রাকচারড)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
struct Vertex { char label; bool visited; };
struct Vertex* lstVertices[MAX];
int adjMatrix[MAX][MAX];
int vertexCount = 0;
int stack[MAX], top = -1;
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* v = malloc(sizeof(struct Vertex));
v->label = label; v->visited = false;
lstVertices[vertexCount++] = v;
}
void addEdge(int s, int e) {
adjMatrix[s][e] = adjMatrix[e][s] = 1;
}
int getAdjUnvisitedVertex(int v) {
for (int i = 0; i < vertexCount; i++)
if (adjMatrix[v][i] == 1 && !lstVertices[i]->visited) return i;
return -1;
}
void displayVertex(int v) { printf("%c ", lstVertices[v]->label); }
void depthFirstSearch() {
lstVertices[0]->visited = true;
displayVertex(0);
push(0);
while (!isStackEmpty()) {
int u = getAdjUnvisitedVertex(peek());
if (u == -1) pop();
else {
lstVertices[u]->visited = true;
displayVertex(u);
push(u);
}
}
for (int i = 0; i < vertexCount; i++) lstVertices[i]->visited = false;
}
int main() {
addVertex('S'); addVertex('A'); addVertex('B'); addVertex('C'); addVertex('D');
addEdge(0,1); addEdge(0,2); addEdge(0,3); addEdge(1,4); addEdge(2,4); addEdge(3,4);
printf("Depth First Search: ");
depthFirstSearch();
return 0;
}
আউটপুট
Depth First Search: S A D B C
