Gộp chung đường đi Euler và Chu trình Euler lại bằng Dev C++

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạ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 xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.

Thuật toán Euler - tìm đường đi Euler, chu trình Euler trên đồ thị G (với đồ thị nửa Euler)

Có file đính kèm phía dưới

#include<iostream>

#include<conio.h>

using namespace std;

#define MAX 50

#define TRUE 1

#define FALSE  0

int A[MAX][MAX], n, u;

void Init(){

 freopen("D:\\G.txt", "r",stdin);

 cin>>n;

 cout<<"So dinh do thi:"<<n<<endl;

 //nh?p ma tr?n k?.

 for(int i=1; i<=n;i++){

  for(int j=1; j<=n;j++){

   cin>>A[i][j];

  }

 }

}

int Kiemtra(){

 int s, d;

 d=0; //bi?n d?m s? d?nh b?t l?.

 for(int i=1; i<=n;i++){

  s=0;

  for(int j=1; j<=n;j++)

   s+=A[i][j];

  if(s%2){

   d++; //tang giá tr? bi?n d?m d?nh b?c l?.

   u=i; //Ghi nh? d?nh b?c l?.

  }

 }

 if(d!=2) return(FALSE); //n?u s? d?nh b?c l? khác 2 thì không có du?ng di Euler.

 return(TRUE);

}

void DDEULER(){

 int v, x, top, dCE;

 int stack[MAX], CE[MAX];

 top=1;

 stack[top]=u;// n?p d?nh b?c l? vào trong stack.

 dCE=0;

 do {

  v = stack[top];// l?y d?nh v ra kh?i stack.

  //tìm d?nh x k? v?i v.

  x=1;

  while (x<=n && A[v][x]==0)

   x++;

  //n?u d?nh x không k? v?i v -> l?y v ra kh?i stack và dua vào CE.

  if (x>n) {

   dCE++; CE[dCE]=v; top--;

  }

  //n?u d?nh x k? v?i d?nh v -> dua x vào stack và xóa c?nh (v,x).

  else {

   top++; stack[top]=x;

   A[v][x]=0; A[x][v]=0;

  }

 } while(top!=0);

 cout<<" Co duong di Euler:";

 //In k?t qu? ch?a trong CE theo th? t? ngu?c l?i.

 for(x=dCE; x>0; x--)

  cout<<(char)(CE[x] + 'a' - 1)<<" "; //in ra k?t qu? du?i d?ng char.

}


void Tim(){

 int v, x, top, dCE;

 int stack[MAX], CE[MAX];

 top=1;

 stack[top]=u;

 dCE=0;

 do {

  v = stack[top];

  x=1;

  while (x<=n && A[v][x]==0)

   x++;

  if (x>n) {

   dCE++;

   CE[dCE]=v;

   top--;

  }

  else {

   top++;

   stack[top]=x;

   A[v][x]=0;

   A[x][v]=0;

  }

 } while(top!=0);

 cout<<" Co chu trinh Euler:";

 for(x=dCE; x>0; x--)

  cout<<(char)(CE[x] + 'a' - 1)<<" ";

}

int main(){

 Init();

 if(Kiemtra()) {
      DDEULER();
 } else
 {
     printf("Khong co duong di Euler");
 }
 
 
  if(Kiemtra()){
      Tim();
  } else {
      printf("Khong co chu trinh Euler");
  }

 _getch();

}

Hình đính kèm kết quả