[Thuật toán] Tìm đường đi và Chu trình Euler

Để 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.
Đị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

Đồ 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

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

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.