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

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.
Image CAPTCHA
Enter the characters shown in the image.

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

 
Drupal Disruptive Open Source: Part I — From Brobdingnag to Lilliput

Mã nguồn mở Drupal Disruptive: Phần 1- từ Brobdingnag đến Lilliput

Drupal's founder, Dries Buytaert, in his keynote at the 2010 San Francisco Drupalcon, asked the rhetorical question: Is Drupal a disruptive technology?

Kích ngầm lắp đặt tuyến ống nước sạch D2400 mm băng sông Sài Gòn

Khởi công dự án cải thiện chất lượng nước sạch Tp. Hồ Chí Minh

Sawaco tổ chức lễ khởi công dự án Thiết kế, cung cấp và lắp đặt tuyến ống truyền tải nước sạch D2400 mm từ ngã tư Bình Thái đến giao lộ Điện Biên Phủ và Nguyễn Bỉnh Khiêm, Tp. Hồ Chí Minh.

Facebook

Mỗi ngày Facebook xử lí hơn 500 TB dữ liệu

Jay Parikh, Phó Chủ tịch phụ trách cơ sở hạ tầng kĩ thuật của Facebook đã thống kê một danh sách cho thấy số dữ liệu khổng lồ mà bộ phận này này phải xử lí mỗi ngày.

Tomdesgin.vn

 

Drupal Services