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: 5.9 (73 votes)
Ảnh của Tommy Tran

Tommy 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

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

 
Hướng dẫn Ghost - chia sẻ dữ liệu trên máy ảo

Hướng dẫn Ghost - chia sẻ dữ liệu trên máy ảo

Vậy là bạn đã hoàn thành Ghost cho 1 máy ảo mới và cách phân vùng, chia ổ, chia sẻ dữ liệu giữa máy thật và ảo rồi đó.Đôi chút kinh nghiệm chia sẻ cùng mọi người, hi vọng sẽ giúp ích được cho mọi người. Trên đây cũng mong nhận được góp ý của mọi người để mình khắc phục những hạn chế và điểm mạnh của bản thân.

Book: Front End Drupal, Designing, Theming and Scripting

Download sách Drupal: Theming and Scripting, Designing

Drupal faces a common problem on the Web–the relative lack of new, high quality themes. Front End Drupal tackles this problem directly and is designed to help both experienced designers and rank novices get an understanding of how Drupal theming works. In fact, I’ll be the first to admit I learned a lot from this book.

Hiển thị thứ hạng Alexa cho website Drupal bằng module Alexa4drupal

Hiển thị thứ hạng Alexa cho website Drupal bằng module Alexa4drupal

Trong bài viết Thêm sắc màu cho web site Joomla! của bạn (Phần 1) đã có giới thiệu về cách sử dụng My Alexa Data để có thể hiện thị thứ hạng của Alexa cho website trên Joomla! nhưng hôm nay chúng tôi sẽ giới thiệu cách hiện thị thứ hạng Alexa trên một website bằng Drupal (giống như giao diện mới hiện tại của thông tin công nghệ được xây dựng trên Drupal).

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

 

Diet con trung