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?: 
Average: 10 (1 vote)
Ả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

Filtered HTML

  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Các thẻ HTML được chấp nhận: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Tự động ngắt dòng và đoạn văn.

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.
Image CAPTCHA
Enter the characters shown in the image.

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

 
“Bình” mới, “rượu” sẽ mới!

“Bình” mới, “rượu” sẽ mới!

Gần đây, “ma lực” giảm giá đến 90% của các website “mua hàng theo nhóm” - groupon đã tạo thêm nguồn sinh lực cho thương mại điện tử Việt Nam.

Chọn SEO Web Hay PPC Cho Website ?

Chọn SEO Web Hay PPC Cho Website ?

Cộng đồng mạng là một thị trường rất lớn mà bạn không thể bỏ qua, đặc biệt khi bạn kinh doanh trực tuyến. Thị trường này có hàng triệu nếu không muốn nói là có hàng tỷ khách hàng tiềm năng.

Quản lý cookies là một phần quan trọng nhưng cơ bản cần được thực hiện để bảo vệ thông tin cá nhân của mình.

Xóa Cookies trên Safari

Quản lý cookies là một phần quan trọng nhưng cơ bản cần được thực hiện để bảo vệ thông tin cá nhân của mình.

Công ty diệt chuột T&C

 

Diet con trung