Kiểm Tra Tính Liên Thông Của đồ Thị G - VN SEEDER

VN SEEDER

Chắc chắn là có đủ....

Menu

• Tin học - Lập trình
  • Lập trình căn bản
  • Lập trình đồ họa
  • Cấu trúc dữ liệu & giải thuật
  • C# và SQL Server
  • Thủ thuật máy tính
• Kiến thức
  • Có thể bạn chưa biết
  • Làm thế nào
  • Nuôi dạy con
  • Sức khỏe
• Đọc
  • Hạt giống tâm hồn
  • Truyện cổ tích
  • Truyện cười
  • Truyện ngụ ngôn
  • Tony buổi sáng
  • Phật học
• Ebook
  • English Ebook
  • Vietnamese Ebook

Trang chủ >> Cấu trúc dữ liệu và giải thuật >> Thuật toán >> Kiểm tra tính liên thông của đồ thị G Kiểm tra tính liên thông của đồ thị G Từ khóa Cấu trúc dữ liệu và giải thuật Thuật toán

Mô tả bài toán: Cho đồ thị vô hướng G = (V,E) hãy kiểm tra tính liên thông của đồ thị G.Ý tưởng thuật toán: Bước 1: xuất phát từ một đỉnh bất kỳ của đồ thị. Ta đánh dấu đỉnh xuất phát và chuyển sang Bước 2. Bước 2: từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang Bước 3. Bước 3: thực hiện Bước 2 cho đến khi không còn thực hiện được nữa chuyển sang Bước 4. Bước 4: kiểm tra nếu số đỉnh đánh dấu nhỏ hơn n (hay tồn tại ít nhất một đỉnh chưa được đánh dấu) đồ thị sẽ không liên thông và ngược lại đồ thị liên thông.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 Input.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: thông báo kết quả ra màn hình ”DO THI LIEN THONG” hay “ DO THI KHONG LIEN THONG”.Ví dụ:#include <stdio.h>#include <conio.h>#include <iostream.h>//doc du lieu tu tap tinvoid Doc_File(int **A,int &n) { FILE*f = fopen("Input.txt","rb"); fscanf(f,"%d",&n); *A = new int [n]; cout<<"Ma Tran Lien Ket Cua Do Thi"; for(int i =0;i<n;i++) { A[i] = new int [n]; cout<<endl; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<" "<<A[i][j]; } }fclose(f);}//kiem tra tinh lien thong neu lien thong tra ve gia tri 1 nguoc lai tra ve gia tri 0char Lien_Thong(int **A,int n) { char*DanhDau = new char [n]; char ThanhCong; int Dem=0; for(int i = 0; i<n; i++) //Khoi tao moi dinh chua danh dau DanhDau[i] = 0; DanhDau[0] = 1; //danh dau dinh dau Dem++; //dem so dinh duoc danh dau do { ThanhCong =1; //khong con kha nang loang for(i = 0; i<n; i++) if(DanhDau[i]==1) { for(int j = 0; j<n; j++) if (DanhDau[j] == 0 && A[i][j] > 0) { DanhDau[j] = 1; ThanhCong = 0; //con kha nang loang Dem++; if(Dem == n) return 1; } } }while (ThanhCong == 0); //lap lai cho den khi khong con kha nang loan return 0;}//chuong trinh chinhvoid main(){ clrscr(); int **A,n; Doc_File(A,n); if (Lien_Thong(A,n)==1) cout<<"\nDO THI LIEN THONG"; else cout<<"\nDO THI KHONG LIEN THONG"; delete *A; getch();}

Bài liên quan

Bài liên quan

>

Thể loại

Cổ tích Có thể bạn chưa biết Nuôi - Dạy con TonyBuổi Sáng-TnBS Sức khỏe Máy tính Lập trình căn bản Làm thế nào Ngẫm Cấu trúc dữ liệu và giải thuật Hạt giống tâm hồn C# và SQL Server Phật học Truyện ngụ ngôn Giáo dục

Ebook Tiếng Anh

CSharp Facebook SEO Windows

Bài xem nhiều

• Lập trình căn bản C: Tìm ước chung lớn nhất, bội chung nhỏ nhất của 2 số a, b
• Lập trình căn bản C: Rút gọn phân số
• Lập trình căn bản C: Xét trúng tuyển thi đại học
• Những lần xê dịch
• Lập trình căn bản C: In ra n số nguyên tố đầu tiên
• Chuyện tiền chuyện bạc (phần 2)
• Lập trình căn bản C: in tam giác số đối đỉnh
• Lập trình căn bản C: tìm số m lớn nhất sao cho tổng từ một đến m nhỏ hơn bằng n
• Làm Menu lựa chọn bằng mũi tên di chuyển lên xuống C/C++
• Đảo ngược số nguyên dương bằng cách sử dụng đệ quy (có trả về kết quả)

top