File đính kèm tìm chu trình Euler của đồ thị vô hướng G=(V,E)

File đính kèm tìm chu trình Euler của đồ thị vô hướng G=(V,E)

Mô tả bài toán:

cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần.

Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.

Mô tả dữ liệu đầu vào và đầu ra của bài toán:

+ Dữ liệu vào: cho trong tập tin D:\\G.txt

   - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)

   - Dòng i+1 (1 <= i <= n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.

+ Dữ liệu ra: in ra màn hình đường đi qua tất cả các cạnh (nếu có).

do thi euler

Cài đặt

#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("D:\\G.txt","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];//d?m các b?c c?a các d?nh c?a d? th?

  if(s%2) d++;

 }

 if(d>0) return(FALSE); //N?u có 1 d?nh b?c l? thì d? th? không có chu trình Euler.

 return(TRUE); //N?u t?t c? các d?nh c?a d? th? là ch?n thì d? 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 d?nh u vào stack.

 dCE=0;

 do {

  v = stack[top];//l?y d?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 d?nh k? v?i d?nh v.

   x++;

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

   dCE++;

   CE[dCE]=v;//luu d?nh v vào m?ng k?t qu? duy?t CE.

   top--;

  }

  else { //d?nh x là d?nh k? v?i d?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? du?i d?ng char.

}

int main(void){

 Init();

 if(Kiemtra())

  Tim();

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

 _getch();

}

Kết quả

ket qua euler

Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ả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

 

3 tháng không mua được nhà và ảo tưởng làm giàu bằng bất động sản

Suốt 3 tháng nay, tôi ngán ngẩm khi không tìm mua được nhà vì người bán lỳ đòn, chỉ muốn cắt lời, không chịu cắt lỗ.

5 năm chiếc điện thoại ‘thay đổi thế giới’ ra đời

5 năm chiếc điện thoại ‘thay đổi thế giới’ ra đời

Vào ngày này 5 năm về trước, Apple công bố sẽ cho ra mắt chiếc điện thoại làm thay đổi thị trường smartphone và đến thời điểm hiện tại, điều đó đúng.

CMS Drupal, Audio, Video, TinyMCE's Media Plugin

Chèn Audio và Video trong Drupal với TinyMCE's Media Plugin

If you have TinyMCE installed on your Drupal site, you have all you need to upload and play audio and video files.

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

 

Diet con trung