Tìm kiếm theo chiều rộng trong C

Trang trước
Trang sau  

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 rộng.

Tìm kiếm theo chiều rộng trong C

Tìm kiếm theo chiều rộng trong C

#include 
#include 
#include #define MAX 5struct Vertex {
   char label;
   bool visited;
};//khai bao cac bien cho hang doi (queue)int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;//khai bao cac bien cho 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];//mot bien de dem so dinh (vertex)
int vertexCount = 0;
//cac ham thao tac tren hang doi (queue)void insert(int data) {
   queue[++rear] = data;
   queueItemCount++;
}int removeData() {
   queueItemCount--;
   return queue[front++]; 
}bool isQueueEmpty() {
   return queueItemCount == 0;
}//cac ham thao tac tren do thi (graph)//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 cac 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; ivisited == false)
         return i;
   }
	
   return -1;
}void breadthFirstSearch() {
   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 hang doi
   insert(0);
   int unvisitedVertex;   while(!isQueueEmpty()) {
      //Rut dinh chua duoc duyet tu hang doi
      int tempVertex = removeData();         //khong tim thay dinh lien ke
      while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }
		
   }      //hang doi la trong, hoan thanh tim kiem, reset gia tri cua visited        
   for(i = 0;ivisited = false;
   }    
}int main() {
   int i, j;   for(i = 0; i

Kết quả


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

Tìm kiếm theo chiều rộng trong C




 Trang trước






Trang sau  



giai-thuat-tim-kiem-theo-chieu-rong.jsp



	
Bài viết liên quan