Thuật toán về tìm đường đi và Chu trình Euler bằng C/C++

Thuật toán về tìm đường đi và Chu trình Euler bằng C/C++

Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây.

>> Thuật toán về duyệt các thành phần liên thông của đồ thị bằng C/C++

Định nghĩa: Chu trình đơn trong đồ thị G đi qua mỗi cạnh của đồ thị đúng một lần được gọi là chu trình Euler. Đường đi đơn trong G đi qua mỗi cạnh của nó đúng một lần được gọi là đường đi Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler. Đồ thị có đường đi Euler được gọi là nửa Euler. Rõ ràng, mọi đồ thị Euler đều là nửa Euler nhưng điều ngược lại không đúng.

Chu trình Euler

Chu trình Euler

Đồ thị G1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị G3 không có chu trình Euler nhưng chứa đường đi Euler a, c, d, e, b, d, a, b vì thế G3 là nửa Euler. G2 không có chu trình Euler cũng như đường đi Euler.

Định lý. Đồ thị vô hướng liên thông G=(V, E) là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Đồ thị vô hướng liên thông G=(V, E) là đồ thị nửa Euler khi và chỉ khi nó không có quá hai đỉnh bậc lẻ.

Để tìm một chu trình Euler, ta thực hiện theo thuật toán sau:

*Tạo một mảng CE để ghi đường đi và một stack để xếp các đỉnh ta sẽ xét. Xếp vào đó một đỉnh tuỳ ý u nào đó của đồ thị, nghĩa là đỉnh u sẽ được xét đầu tiên.

*Xét đỉnh trên cùng của ngăn xếp, giả sử đỉnh đó là đỉnh v và thực hiện:

  • Nếu v là đỉnh cô lập thì lấy v khỏi ngăn xếp và đưa vào CE;
  • Nếu v là liên thông với đỉnh x thì xếp x vào ngăn xếp sau đó xoá bỏ cạnh (v, x);

*Quay lại bước 2 cho tới khi ngăn xếp rỗng. Kết quả chu trình Euler được chứa trong CE theo thứ tự ngược lại.

Thủ tục Euler_Cycle sau sẽ cho phép ta tìm chu trình Euler.

void  Euler_Cycle(void){

 Stack:=φ; CE:=φ;

 Chọn u là đỉnh nào đó của đồ thị;

 u=>Stack; /* nạp u vào stack*/

 while (Stack≠φ) { /* duyệt cho đến khi stack rỗng*/

  x= top(Stack); /* x là phần tử đầu stack */

  if (ke(x) ≠ φ) ) {

   y = Đỉnh đầu trong danh sách ke(x);

   Stack<=y; /* nạp y vào Stack*/

   Ke(x) = Ke(x) \{y};

   Ke(y) = Ke(y)\{x}; /*loại cạnh (x,y) khỏi đồ thị}*/

  }

  else {

   x<= Stack; /*lấy x ra khỏi stack*/;

   CE <=x; /* nạp x vào CE;*/

  }

 }

Thuật toán tìm chu trình Euler

Thuật toán tìm chu trình Euler

Bước Giá trị trong Stack Giá trị trong CE Cạnh còn lại
1 f   1, 2, 3, 4, 5, 6, 7, 8, 9, 10
2 f, a   2, 3, 4, 5, 6, 7, 8, 9, 10
3 f, a, c   3, 4, 5, 6, 7, 8, 9, 10
4 f,a,c,f   3, 4, 5, 6, 7, 9, 10
5 f, a, c f 3, 4, 5, 6, 7, 9, 10
6 f, a, c, b f 3, 4, 6, 7, 9, 10
7 f, a, c, b, d f 3, 4, 7, 9, 10
8 f, a, c, b, d,c f 3, 4, 7, 10
9 f, a, c, b, d f, c 3, 4, 7, 10
10 f, a, c, b, d, e f, c 3, 4, 7
11 f, a, c, b, d, e, b f, c 3, 4
12 f, a, c, b, d, e, b, a f, c 3
13 f, a, c, b, d, e, b, a, d f, c  
14 f, a, c, b, d, e, b, a f, c, d  
15 f, a, c, b, d, e, b f, c, d, a  
16 f, a, c, b, d, e f, c, d, a, b  
17 f, a, c, b, d f, c, d, a, b, e  
18 f, a, c, b f, c, d, a, b, e, d  
19 f, a, c f, c, d, a, b, e, d, b  
20 f, a f, c, d, a, b, e, d, b, c  
21 f f, c, d, a, b, e, d, b,c, a  
22   f, c, d, a, b, e, d, b, c, a, f  

Chương trình tìm chu trình 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=1;

void Init(void){

 freopen("CTEULER.IN","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];//đếm các bậc của các đỉnh của đồ thị

  if(s%2) d++;

 }

 if(d>0) return(FALSE); //Nếu có 1 đỉnh bậc lẻ thì đồ thị không có chu trình Euler.

 return(TRUE); //Nếu tất cả các đỉnh của đồ thị là chắn thì đồ 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 đỉnh u vào stack.

 dCE=0;

 do {

  v = stack[top];//lấy đỉ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 đỉnh kề với đỉnh v.

   x++;

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

   dCE++;

   CE[dCE]=v;//lưu đỉnh v vào mảng kết quả duyệt CE.

   top--;

  }

  else { //đỉnh x là đỉnh kề với đỉ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ả dưới dạng char.

}

void main(void){

 Init();

 if(Kiemtra())

  Tim();

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

 _getch();

}

Ma trận kề của đồ thị

6

0 1 1 1 1 0

1 0 1 1 0 1

1 1 0 1 1 0

1 1 1 0 0 1

1 0 1 0 0 0

0 1 0 1 0 0

Out put của chương trình:

So dinh cua do thi n = 6

Co chu trinh Euler : a b c a d b f d c e a

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();

}

Để tìm tất cả các đường đi Euler của một đồ thị n đỉnh, m cạnh, ta có thể dùng kỹ thuật đệ qui như sau:

Bước 1.Tạo mảng b có độ dài m + 1 như một ngăn xếp chứa đường đi. Đặt b[0]=1, i=1(xét đỉnh thứ nhất của đường đi);

Bước 2.Lần lượt cho b[i] các giá trị là đỉnh kề với b[i-1] mà cạnh (b[i-1],b[i]) không trùng với những cạnh đã dùng từ b[0] đến b[i-1]. Với mỗi giá trị của b[i], ta kiểm tra:

  • Nếu i < m thì tăng i lên 1 đơn vị (xét đỉnh tiếp theo) và quay lại bước 2.
  • Nếu i == m thì dãy b chính là một đường đi Euler.

Chương trình liệt kê tất cả đườ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 n;//số đỉnh của đồ thị.

int m;//số cạnh của đồ thị.

int b[MAX];//mảng b có độ dài m + 1 phần tử.

int u;//đỉnh bậc lẻ trong đồ thị

int OK;//biến kiểm tra đồ thị có đường đi EULER hay không.

int A[MAX][MAX];//ma trận kề của đồ thị.

int i;

void Init(){

 freopen("DDEULER.IN", "r",stdin);

 cin>>n;

 cout<<"So dinh do thi:"<<n;

 // nhập ma trận kề.

 int s;//biến đếm số bậc của đỉnh i.

 int d = 0;//biến đếm số đỉnh bậc lẻ.

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

  int s = 0;

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

   cin>>A[i][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ẻ.

  }

  m=m+s;

 }

 m=m /2;

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

 else OK=TRUE;

}

void Result(void){

 cout<<"Co duong di Euler:";

 for(int i=0; i<=m; i++)

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

 cout<<endl;

}

void DDEULER(int i){

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

  if (A[b[i-1]][j]==1){

   A[b[i-1]][j]=0;

   A[j][b[i-1]]=0;

   b[i]=j;

   if(i==m){

    Result();

   }

   else{

    DDEULER(i+1);

   }

   A[b[i-1]][j]=1;

   A[j][b[i-1]]=1;

  }

 }

}

void main(void){

 Init();

 b[0]=u;//Gán b[0] nhận giá trị là đỉnh lẻ của đồ thị.

 i=1;

 if(OK) DDEULER(i);

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

 getch();

}

 

Bạn thấy bài viết này như thế nào?: 
Average: 6.1 (19 votes)
Ả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.
7 + 3 =
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

 
Thời đại Big Data - Amazon đạt doanh thu tới 74 tỷ USD

Thời đại Big Data - Amazon đạt doanh thu tới 74 tỷ USD

Thế giới đang bước vào kỷ nguyên Big Data, khi các quyết định được đưa ra không dựa trên chuyên gia mà dựa vào các tập hợp dữ liệu lớn. 

Amazon gia tăng sản xuất Kindle Fire

Amazon gia tăng sản xuất Kindle Fire

Doanh số bán hàng mạnh mẽ của máy tính bảng Kindle Fire đã khiến Amazon phải tăng các đơn đặt hàng của mình, chứng minh rằng mọi người thực sự thích máy tính bảng giá rẻ.

Tính năng nổi bật và mô hình hoạt động của Cloud Hosting

Tính năng nổi bật và mô hình hoạt động của Cloud Hosting

Cloud Hosting hoạt động trên nền điện toán đám mây (cloud computing), sử dụng nền tảng máy chủ tốt nhất của Dell, Cisco,IBM,Supermicro cùng với hệ thông lưu trữ SAN, hoạt động trên hệ điều hành CloudLinux

BLOG POSTS

 

Wordpress Freelancer

 

Wordpress Freelancer