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 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

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.
7 + 12 =
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

 
Cài đặt Dropbox trên "ngọn lửa" Kindle Fire của Amazon

Cài đặt Dropbox trên "ngọn lửa" Kindle Fire của Amazon

Bạn đang có ý muốn truy cập tất cả các tập tin trên "ngọn lửa" Kindle Fire của Amazon từ tài khoản Dropbox.

Anchor Text

Anchor Text

Anchor text is the visible characters and words that hyperlink display when linking to another document or location on the web

10 điều top nhất bạn có thể mang đến DrupalCon! Austin!

10 điều top nhất bạn có thể mang đến DrupalCon! Austin 2014

You're about to enjoy 3,000 PLUS ppl getting their Drupal on! This will be my 7th year at DrupalCon. 

Tomdesgin.vn

 

Drupal Services