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.
12 + 8 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
phong thi nghiem sawaco

Ứng dụng công nghệ giám sát chất lượng nước tại Phòng thí nghiệm Tổng Công ty Cấp nước Sài Gòn TNHH MTV

Tổng công ty Cấp nước Sài Gòn (Sawaco) thực hiện nhiều biện pháp để theo dõi, kiểm tra chất lượng nhằm đảm bảo cung cấp nước sạch đến người tiêu dùng luôn đáp ứng theo yêu cầu về chuẩn kỹ thuật quốc gia do Bộ Y tế quy định. 

Chrome trên iOS

Thêm tính năng chia sẻ mới cho Chrome trên iOS

Bản cập nhật mới nhất của trình duyệt Chrome cho hệ điều hành iOS ngoài việc sửa một số lỗi nhỏ thì sẽ bổ sung thêm một tính năng mới rất tiện dụng. Đó là người dùng có thể chia sẻ các trang web xem từ trình duyệt Chrome lên Google+, email, Facebook và Twitter.

Apple phát hành bản cập nhật Java

Apple phát hành bản cập nhật Java

Java cho Mac OS X 10.7 Update 1, phát hành hôm thứ 3 ngày 8/11, cập nhật phần mềm cho phiên bản 1.6.0_29, và cung cấp một số cải thiện về độ tin cậy, bảo mật, khả năng tương thích cho người dùng Mac OS X Lion.

Wordpress Freelancer

 

Wordpress Freelancer