File đính kèm tìm đường đi Euler trên đồ thị G (với đồ thị nửa Euler)

File đính kèm tìm đường đi Euler trên đồ thị G (với đồ thị nửa Euler)

Một đồ thị không có chu trình Euler nhưng vẫn có thể có đường đi Euler. Khi đó, đồ thị có đúng hai đỉnh bậc lẻ, tức là tổng các số cạnh xuất phát từ một trong hai đỉnh đó là số lẻ. Một đường đi Euler phải xuất phát từ một trong hai đỉnh đó và kết thúc ở đỉnh kia. Như vậy, thuật toán tìm đường đi Euler chỉ khác với thuật toán tìm chu trình Euler ở chỗ ta phải xác định điểm xuất phát của đường đi từ đỉnh bậc lẻ này và kết thúc ở đỉnh bậc lẻ khác.

Chương trình tìm đường đi Euler được thể hiện như sau:

#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("DDEULER.IN", "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 đếm số đỉ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++; //tăng giá trị biến đếm đỉnh bậc lẻ.

   u=i; //Ghi nhớ đỉnh bặc lẻ.

  }

 }

 if(d!=2) return(FALSE); //nếu số đỉnh bậc lẻ khác 2 thì không có đường đi Euler.

 return(TRUE);

}

void DDEULER(){

 int v, x, top, dCE;

 int stack[MAX], CE[MAX];

 top=1;

 stack[top]=u;// nạp đỉnh bậc lẻ vào trong stack.

 dCE=0;

 do {

  v = stack[top];// lấy đỉnh v ra khỏi stack.

  //tìm đỉnh x kề với v.

  x=1;

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

   x++;

  //nếu đỉnh x không kề với v -> lấy v ra khỏi stack và đưa vào CE.

  if (x>n) {

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

  }

  //nếu đỉnh x kề với đỉnh v -> đưa 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ự ngược lại.

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

  cout<<(char)(CE[x] + 'a' - 1)<<" "; //in ra kết quả dưới dạng char.

}

void main(void){

 Init();

 if(Kiemtra())

  DDEULER();

 else printf("Khong co duong di Euler");

 _getch();

}

Ví dụ không có chu trình mà có đường đi

Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ảnh của Khanh Hoang

Khanh Hoang - Kenn

Kenn is a user experience designer and front end developer who enjoys creating beautiful and usable web and mobile experiences.

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.

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

 
Customize display và form modes trong  Drupal 8

Customize display và form modes trong Drupal 8

Last week as I was looking over the Drupal 8 landing page on Drupal.org, I noticed a section titled "Customize display and form modes" and my curiosity was piqued. I fired up an instance of Drupal 8 on Simplytest.me to take a look.

Google sắp tung ra dịch vụ lưu trữ trực tuyến

Google sắp tung ra dịch vụ lưu trữ trực tuyến

Theo thông tin của một tờ báo uy tín, Google sẽ sớm tung ra một dịch vụ lưu trữ đám mây, cạnh tranh trực tiếp với Dropbox hay Box.net.

Apple thử nghiệm máy tính bảng màn hình nhỏ

Apple thử nghiệm máy tính bảng màn hình nhỏ

Tập đoàn Apple đang hợp tác với các nhà cung cấp linh kiện ở Châu Á để thử nghiệm môt loại máy tính bảng mới với màn hình nhỏ hơn trong nỗ lực tìm kiếm mở rộng dòng sản phẩm trong bối cảnh cạnh tranh khốc liệt...

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

 

Diet con trung