การใช้งาน DFS โดยใช้ภาษา C

Depth First Search (DFS) เป็นอัลกอริธึมที่สำรวจกราฟและไปที่โหนดทั้งหมดก่อนที่จะกลับมาสามารถระบุได้ นอกจากนี้ยังกำหนดว่ามีเส้นทางระหว่างสองโหนดหรือไม่

มันค้นหากราฟหรือต้นไม้ในลักษณะเชิงลึก

อัลกอริทึม

ด้านล่างนี้เป็นอัลกอริทึมสำหรับการนำ Depth First Search (DFS) ไปใช้ -

ขั้นตอนที่ 1 − สแต็คแรกว่างเปล่า

ขั้นตอนที่ 2 − หากไม่มีโหนดที่จะเยี่ยมชมในสแต็ก เราจะดันโหนดนั้นไปที่สแต็กและทำเครื่องหมายว่าเยี่ยมชมแล้ว

ขั้นตอนที่ 3 − จากนั้นตรวจสอบว่าโหนดปัจจุบันตรงกับเกณฑ์การค้นหาของเราหรือไม่

ขั้นตอนที่ 3.1 − ถ้ามันอยู่ที่นั่น แสดงว่าเราทำเสร็จแล้ว

ขั้นตอนที่ 4 − มิฉะนั้น เราต้องไปที่โหนดที่อยู่ติดกันทั้งหมดจากโหนดปัจจุบัน

ขั้นตอนที่ 4.1 − จากนั้นไปที่โหนดทุกประเภท สุ่มลำดับและทำการค้นหาต่อไป

ขั้นตอนที่ 5 − หากโหนดที่อยู่ติดกันทั้งหมดได้รับการเยี่ยมชมแล้ว โหนดนั้นจะกลายเป็นทางตัน

ขั้นตอนที่ 6 − เราไปที่โหนดที่เข้าชมก่อนหน้านี้และเปิดโหนดล่าสุดจากสแต็ก

ขั้นตอนที่ 7 − อัลกอริทึมจะยุติการทำงานหากมีการค้นหาโหนดทั้งหมด หรือหากเราได้รับคำตอบ

โปรแกรม

ต่อไปนี้เป็นโปรแกรม C สำหรับ การใช้งาน Depth First Search (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;
};
//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