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

 
Cài đặt Nginx với PHP5, PHP-FPM và hỗ trợ MySQL trên Ubuntu 11.10

Cài đặt Nginx với PHP5, PHP-FPM và hỗ trợ MySQL trên Ubuntu 11.10

Nginx (phát âm "engine x") là một chương trình server HTTP, một reverse proxy cũng như IMAP/POP3 proxy server miễn phí, mã nguồn mở, có hiệu năng cao.

Drupal 7 – Part 1: giúp bạn tăng production speed and efficiency trong kinh doanh

Drupal 7 – Part 1: giúp bạn tăng production speed and efficiency trong kinh doanh

Your time-to-market can be the difference between success and failure in today’s rapidly changing and evolving business world

Kiếm tiền từ cộng đồng mạng - nhiều tiềm năng

Kiếm tiền từ cộng đồng mạng - nhiều tiềm năng

Theo nghiên cứu của Yahoo - Kantar Media, 55% số người dùng Internet truy cập vào các mạng xã hội năm 2011, so với 41% năm 2010. Đầu tư vào các website có cộng đồng đã trở nên hấp dẫn!

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

 

Diet con trung