SỬ DỤNG STACK VÀO THUẬT TOÁN DUYỆT THEO CHIỀU RỘNG TÌM MỌI ĐƯỜNG ĐI HAMILTON CỦA ĐỒ THỊ VÔ HƯỜNG G

BÀI TOÁN
Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh xuấtphát đi qua tất cả các đỉnh mỗi đỉnh chỉ qua duy nhất 1 lần.
Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách đánh dấu đỉnh đã đi qua trong quá trình tìm kiếm.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: cho trong tập tin Bai4.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng 2 ghi đỉnh xuất phát.
- Dòng i+2 (1 <= i <= n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: in ra màn hình đường đi qua tất cả các đỉnh (nếu có).
Ví dụ:
INPUT
Bai4.inp
6
1
0 1 1 0 0 0
1 0 1 0 1 0
1 1 0 0 0 1
0 0 0 0 1 0
0 1 0 1 0 0
0 0 1 0 0 0
OUTPUT
KHONG TON TAIDUONG DI
INPUT
5
1
0 1 0 0 0
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
OUTPUT
1->2->3->4->5
1->2->5->4->3

MÔ TẢ CÁC CHỨC NĂNG CỦA BIẾN
    Stack S: dùng để lưu vết đường đi trong quá trình duyệt.
    Stack L: dùng để lưu đừng đi
    F: sử dụng để chỉ khả năng còn đi tiếp
    M: đánh dấu đỉnh đã đi qua

TÌM MỌI ĐƯỜNG ĐI HAMILTON

Code:

//Find all routes Hamilton on graphic
void Hamilton(char **A, unsigned int n, unsigned int Start) {
   Stack S = MakeNull_Stack();
   Stack L = MakeNull_Stack();
   unsigned int Count = 0;
   char F = 0;
   Push(Start,S);
   char *M = new char[n];
   for(int i = 0; i<n; i++)
      M[i] = 0;
   while(!Empty_Stack(S)) {
      if(!Empty_Stack(S)) {
         Start = Top(S);
         Push(Start,L);
         M[Start] = 1;
         Count++;
      }
      if(Count<n)
      {
         F = 0;
         for(i=0; i<n; i++)
         if(A[Start][i]==1 && M[i]==0)
         {
            Push(i,S);
            F = 1;
         }
      }
      if(Count==n || F==0) {
         if(Count == n) {
            printf("\n");
            Out_Stack(L);
         }
         while(!Empty_Stack(S) && Top(S) == Top(L)) {
            M[Top(S)] = 0;
            Pop(S);
            Pop(L);
            Count--;
         }
      }
   }
}

CHƯƠNG TRÌNH MẪU

Code:

#include "conio.h"
#include "stdio.h"
#include "alloc.h"
#define FileIn "Graph.inp"
typedef int ElementType;
typedef struct Node {
   ElementType Element;
   Node *Next;
};
typedef Node *Stack;
//Make null a stack
Stack MakeNull_Stack(){
   Stack Header = (Node*)malloc(sizeof(Node));
   (Header)->Next = NULL;
   return Header;
}
//Result 1 if stack is null else result 0
char Empty_Stack(Stack S) {
   return S->Next == NULL;
}
//Init a node
Node *Make_Node(ElementType X) {
   Node *temp = (Node*)malloc(sizeof(Node));
   temp->Element = X;
   return temp;
}
//Insert a element on top stack
void Push(ElementType X, Stack P) {
   Node *temp = Make_Node(X);
   temp->Next = P->Next;
   P->Next = temp;
}
//Delete a element from top stop
void Pop(Stack P){
   Stack temp;
   if (!Empty_Stack(P)){
      temp = P->Next;
      P->Next = temp->Next;
      free(temp);
   }
}
//Get a element from a top stack
ElementType Top(Stack S) {
   return S->Next->Element;
}
//Print a stack out screen
void Out_Stack(Stack L) {
   Stack temp = L;
   while(!Empty_Stack(temp)) {
      printf("%d\t",temp->Next->Element+1);
      temp = temp->Next;
   }
}
//Read data from file
void Read_File(char **A, unsigned int &n, unsigned int &Start) {
   FILE*f = fopen(FileIn,"rb");
   fscanf(f,"%d%d",&n,&Start);
   printf("This Matrix\n%d\n",Start);
   *A = (char*)malloc(sizeof(char)*n);
   for(int i =0;i<n;i++) {
      A[i] = (char*)malloc(sizeof(char)*n);
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);
         printf("%d ",A[i][j]);
      }
      printf("\n");
   }
   Start--;
   fclose(f);
}
//Find all routes Hamilton on graphic
void Hamilton(char **A, unsigned int n, unsigned int Start) {
   Stack S = MakeNull_Stack();
   Stack L = MakeNull_Stack();
   unsigned int Count = 0;
   char F = 0;
   Push(Start,S);
   char *M = new char[n];
   for(int i = 0; i<n; i++)
      M[i] = 0;
   while(!Empty_Stack(S)) {
      if(!Empty_Stack(S)) {
         Start = Top(S);
         Push(Start,L);
         M[Start] = 1;
         Count++;
      }
      if(Count<n)
      {
         F = 0;
         for(i=0; i<n; i++)
         if(A[Start][i]==1 && M[i]==0)
         {
            Push(i,S);
            F = 1;
         }
      }
      if(Count==n || F==0) {
         if(Count == n) {
            printf("\n");
            Out_Stack(L);
         }
         while(!Empty_Stack(S) && Top(S) == Top(L)) {
            M[Top(S)] = 0;
            Pop(S);
            Pop(L);
            Count--;
         }
      }
   }
}
//The main programming
void main() {
   clrscr();
   char **A;
   unsigned int n, Start;
   Read_File(A,n,Start);
   printf("Result:");
   Hamilton(A,n,Start);
   getch();
}