Tìm kiếm theo chiều sâu trong C

Sau khi đã theo dõi phần giải thuật trong chương trước, trong chương này chúng ta sẽ cùng tìm hiểu phần triển khai code trong ngôn ngữ C của giải thuật Tìm kiếm theo chiều sâu.

Tìm kiếm theo chiều sâu trong C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 5

struct Vertex {
   char label;
   bool visited;
};

//khai bao cac bien cho ngan xep (stack)

int stack[MAX]; 
int top = -1; 



//khai bao cac bien lien quan toi do thi (graph)

//khai bao danh sach cac dinh (Vertex)
struct Vertex* lstVertices[MAX];

//Khai bao mot ma tran ke (adjacency matrix)
int adjMatrix[MAX][MAX];

//khai bao mot bien de dem so dinh
int vertexCount = 0;

//cac ham thao tac voi ngan xep

void push(int item) { 
   stack[++top] = item; 
} 

int pop() { 
   return stack[top--]; 
} 

int peek() {
   return stack[top];
}

bool isStackEmpty() {
   return top == -1;
}

//cac ham thao tac tren do thi

//them dinh vao danh sach cac dinh
void addVertex(char label) {
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}

//them canh vao mang cac canh
void addEdge(int start,int end) {
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}

//hien thi dinh
void displayVertex(int vertexIndex) {
   printf("%c ",lstVertices[vertexIndex]->label);
}       

//lay dinh chua duyet tu ma tran ke
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;

   //danh dau nut dau tien (first node) la da duyet (visited)
   lstVertices[0]->visited = true;

   //hien thi dinh
   displayVertex(0);   

   //chen chi muc cua dinh vao trong ngan xep
   push(0);

   while(!isStackEmpty()) {
      //Rut dinh chua duoc duyet tu ngan xep
      int unvisitedVertex = getAdjUnvisitedVertex(peek());

      //khong tim thay dinh lien ke
      if(unvisitedVertex == -1) {
         pop();
      }else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }

   //ngan xep la trong, hoan thanh tim kiem, reset gia tri cua visited            
   for(i = 0;i < vertexCount;i++) {
      lstVertices[i]->visited = false;
   }        
}


int main() {
   int i, j;

   for(i = 0; i<MAX; i++)  { // thiet lap cac gia tri
      for(j = 0; j<MAX; j++) // cua ma tran ke la 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("Tim kiem theo chieu sau: ");

   depthFirstSearch(); 

   return 0;   
}

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.