File đính kèm tìm chu trình Euler của đồ thị vô hướng G=(V,E)

File đính kèm tìm chu trình Euler của đồ thị vô hướng G=(V,E)

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.

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 D:\\G.txt

   - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)

   - Dòng i+1 (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 cạnh (nếu có).

do thi euler

Cài đặt

#include<iostream>

#include<conio.h>

using namespace std;

#define MAX 50

#define TRUE 1

#define FALSE  0

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

void Init(void){

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

 cin>>n;

 cout<<" So dinh cua do thi n = "<<n<<endl;

 // nhap ma tran lien ke.

 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;

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

  s=0;

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

   s+=A[i][j];//d?m các b?c c?a các d?nh c?a d? th?

  if(s%2) d++;

 }

 if(d>0) return(FALSE); //N?u có 1 d?nh b?c l? thì d? th? không có chu trình Euler.

 return(TRUE); //N?u t?t c? các d?nh c?a d? th? là ch?n thì d? th? có th? có chu trình Euler.

}

void Tim(){

 int v, x, top, dCE;

 int stack[MAX], CE[MAX];

 top=1;

 stack[top]=u;//thêm d?nh u vào stack.

 dCE=0;

 do {

  v = stack[top];//l?y d?nh trên cùng c?a stack.

  x=1;

  while (x<=n && A[v][x]==0) //tìm trong danh sách nh?ng d?nh k? v?i d?nh v.

   x++;

  if (x>n) { //l?y ra kh?i stack.

   dCE++;

   CE[dCE]=v;//luu d?nh v vào m?ng k?t qu? duy?t CE.

   top--;

  }

  else { //d?nh x là d?nh k? v?i d?nh v.

   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)<<" "; //in ra k?t qu? du?i d?ng char.

}

int main(void){

 Init();

 if(Kiemtra())

  Tim();

 else printf("\n Khong co chu trinh Euler");

 _getch();

}

Kết quả

ket qua euler

Bạn thấy bài viết này như thế nào?: 
No votes yet
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

Bình luận (0)

 

Add Comment

Plain text

  • No HTML tags allowed.
  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Tự động ngắt dòng và đoạn văn.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
5 + 11 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Học Drupal Seo qua 11 khái niệm của www.litado.com

Học Drupal Seo qua 11 khái niệm của www.litado.com

Với gần 400 khái niệm, kỹ thuật, thuật ngữ kinh điển về Seo, Adwords, Analytics, Webmasters Tool, Hosting, Domain....được cập nhập mới nhất cùng với các phần mềm

Hacker trộm thẻ tín dụng mua quà cho người nghèo

Hacker trộm thẻ tín dụng mua quà cho người nghèo

Nhóm tin tặc nổi tiếng Anonymous đang nắm trong tay thông tin chi tiết hàng nghìn thẻ tín dụng, trong đó có cả của Apple, Lực lượng không quân Mỹ…

Federal Cloud Computing: Public hay Private Cloud tốt hơn

Federal Cloud Computing: Public hay Private Cloud tốt hơn

The Capital Beltway is 64 miles of interstate surrounding Washington, D.C. Shaped as a loop (hence the “belt”)

Wordpress Freelancer

 

Wordpress Freelancer