[Thuật toán đồ thị / code C++] Tìm số thành phần liên thông của đồ thị G

Mô tả bài toán:
   Cho đồ thị vô hướng G=(V,E) hãy đếm số thành phần liên thông của đồ thị G.

Ý tưởng thuật toán:
 Bước 0: khởi tạo số thành phần liên thông bằng 0.
 Bước 1: xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông lên 1 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: nếu số số đỉnh đánh dấu bằng n kết thúc thuật toán, ngược lại quay về Bước 1.

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 Bai1.inp
- 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: xuất ra màn hình số thành phần liên thông của đồ thị.

Ví dụ:

[ Cài đặt bài toán - code Turbo C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>

//doc du lieu tu tap tin
void 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);
}

//ham tra ve so thanh phan lien thong cua do thi
int TPLien_Thong(int **A, int n) {
    char*DanhDau = new char [n];

    char ThanhCong;
    int Dem=0, i,j, MLT=0;
    for( i = 0; i<n; i++) //khoi tao cac dinh chua danh dau
        DanhDau[i] = 0;
        do {
           j = 0;
           while(DanhDau[j]==1) //tim 1 dinh chua duoc danh dau
           j++;
           DanhDau[j] = 1; //danh dau dinh tim duoc
           Dem++; //tang so dinh danh dau len 1
           MLT++; //tang so thanh phan lien thong len 1
          do {
              ThanhCong =0;
              for(i = 0; i<n; i++)
                 if(DanhDau[i]==1)
                    for(j = 0; j<n; j++)
                          if (DanhDau[j] == 0 && A[i][j] > 0) {
                               DanhDau[j] = 1;
                               ThanhCong =1;
                               Dem++;
                               if(Dem == n) return MLT;
                           }
             }while (ThanhCong == 1);
         } while(Dem<n); //lap lai khi con dinh chua duoc danh dau
    return MLT;
}

//chuong trinh chinh
void main() {
  clrscr();
   int **A,n;
   Doc_File(A,n);
   cout<<"\nTHANH PHAN LIEN THONG: "<<TPLien_Thong(A,n);
   delete *A;
   getch();

}



/***** LƯU Ý ****/
- File Input.txt được đặt ở thư mục chứa code [Download file Input.txt tại đây], các bạn có thể tạo phải Input.txt khác tùy vào đồ thị mà bạn muốn kiểm tra
- Download code chương trình tại đây
- Khi download, bạn chờ 5s, click BỎ QUA QUẢNG CÁO (SKIN AD)

Chúc các bạn thành công!


[tham khảo ĐH Cửu Long]

Quảng cáo

Загрузка...

Categories

8051 (1) AI (1) AI programming (1) amazon (1) Android (27) ASP (1) Assembly (17) Bài giảng (2) Bài giảng lập trình C và Cpp (16) bài giảng quản lý dự án CNTT (1) bài tập java (1) bài tập lập trình (1) Bài viết hay (62) Bản đồ tư duy (1) Bidvertiser (1) Biểu diễn thuật toán (1) bitcoin (1) blockchain (1) Blockchain là gì (1) Bubble-Sort (1) C (77) C Plus Plus (103) C sharp (11) C++ (3) cấu trúc dữ liệu giải thuật (1) Cây (tree) (2) Cây quyết định (3) CDSL phân tán (1) Chữa bài tập Java (1) code assembly (1) Công nghệ điện toán đám mây (1) Công nghệ lập trình (1) Cơ sở dữ liệu (10) CSS (2) Cuộc cách mạng công nghiệp 4.0 (1) Danh ngôn lập trình (1) Danh sách liên kết (list) (1) Datamining (4) Đại số gia tử và ứng dụng (1) đăng ký Amazon (1) Đăng ký hosting (2) đặt hàng trên Amazon (1) Đệ quy (2) Đồ họa (4) Độ phức tạp của thuật toán (1) ebook-csdl (1) ebook-giaithuat (1) ebook-laptrinh (1) ebook-phancung-mang (1) ebook-tinhocungdung (1) ebook-web (1) Exceptions (1) Genetic Algorithm (1) Giải hệ phương trình tuyến tính (5) giải thuật (3) giải thuật Đệ quy (1) Giáo trình (2) Góc học tập (34) Góc suy ngẫm (1) Google App Engine (2) Heap-Sort (1) Hệ quản trị CSDL (1) Học lập trình (125) Học lập trình C và CPP qua ví dụ (15) học lập trình Java (7) HostGator (1) hợp ngữ (1) HPH (25) HTML (1) Hướng Dẫn Đăng Ký Tên Miền và Host Trên Hostgator (1) hướng dẫn mua host (1) hướng dẫn nhận tiền (1) hướng dẫn payoneer (1) Hướng dẫn sử dụng Emu8086 (1) hướng dẫn viết báo (1) hướng đăng ký tên miền (1) Insert-sort (2) iOS (1) Java (50) Java Căn bản (5) java core (3) Java GUI (1) JavaScript (3) Kiếm tiền online (10) Kỹ thuật đồ họa máy tính (9) Kỹ thuật lập trình (16) kỹ thuật SEO (1) Lập trình 8051 với C/C++ (1) Lập trình căn bản (7) Lập trình Cơ sở dữ liệu (2) Lập trình điều khiển thiết bị (1) Lập trình hợp ngữ (1) Lập trình hướng đối tượng (38) Lập trình hướng đối tượng với Java (6) Lập trình mạng (6) Lập trình mobile (3) Lập trình nhúng (1) Lập trình trí tuệ nhân tạo (1) lập trình vi xử lý (1) lập trình viên (1) Lập trình viên độc lập (1) Luyện thi IC3 (4) Lý thuyết Cơ sở dữ liệu (2) Lý thuyết đồ thị (11) Mạng máy tính (1) Mẹo tìm kiếm trên Google (1) Merge-Sort (1) MS Access (1) Mua hàng trên Amazon (1) Nghiên cứu khoa học (1) ngon-ngu-khac (1) Ngôn ngữ lập trình (1) Nhúng code Assembly trong C\C++ (2) Những lỗi thường gặp khi lập trình (1) Oracle (1) Pascal (3) payoneer (1) people-group (1) phần cứng máy tính (1) PHP (1) Quản lý dự án CNTT (1) Queue (hàng đợi) (1) Quick-Sort (1) Seclection-sort (2) SEO (1) SQL (5) Stack (ngăn xếp) (1) Swift (8) tài liệu CNTT miễn phí (2) Tài liệu tham khảo (2) thanh toán quốc tế (1) Thiết kế Web (2) Thủ thuật máy tính (5) thuattoan-khac (1) Thuật toán (41) Thuật toán di truyền (2) Thuật toán Đệ quy (4) Thuật toán K-Mean (1) Thuật toán khác (9) Thuật toán leo đồi (1) Thuật toán ma trận (7) Thuật toán Sắp Xếp -Sort (9) Thuật toán Tìm kiếm - Search (5) Thương mại điện tử (4) Tiện ích máy tính (3) Tìm hiểu Blockchain (1) Tìm kiếm nhị phân (2) Tìm kiếm tuần tự (Line search) (2) Tin học văn phòng (5) Tin tức công nghệ (7) Tính định thức của ma trận (1) Toán rời rạc (12) Trí tuệ nhân tạo (8) Tự học lập trình Android (14) Tự học lập trình C và CPP (14) tự học lập trình iOS (8) Tự học lập trình java qua các ví dụ (7) Ứng dụng cơ sở dữ liệu (1) VB (2) vẽ ngôi nhà (1) ví dụ Assembly (1) xcode (8) XML (1) Xử lý ma trận (mảng 2 chiều) (7) Xử lý mảng 1 chiều (1) Xử lý ngoại lệ (1)