Cài đặt thuật toán duyệt đồ thị liên thông bằng DFS, BFS, Euler không

Cài đặt thuật toán duyệt đồ thị liên thông bằng DFS, BFS, Euler không

Yêu cầu:

(Có đính kèm file lời giải phía cuối bài viết)

- Đọc file "D:\\G.txt" chứa ma trận kề biểu diễn đơn đồ thị vô hướng G, có dạng sau:

Ví dụ:

4
0 1 0 1
1 0 1 1
0 1 0 0
1 1 0 0

Trong đó:

 + Dòng đầu tiên là số đỉnh

 + Các dòng còn lại biểu diễn ma trận kề của đồ thị G

In ma trân kề vừa đọc được

- Duyệt đồ thị với thuật toán DFS, BFS. In kết qua ra màn hình

- Đếm số thành phần liên thông

- Kiểm tra xem đồ thị có phải là Euler không ?

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

#define max 100

#define FileIn "D:\\G.txt"

using namespace std;
int chuaXet[max];

// A: ma tran ke cua G, n: so dinh
int A[max][max], n;

// doc file chua do thi G luu vao ma tran A

void Doc_File(int A[max][max], int &n)
{
  FILE *f = fopen(FileIn, "rb");
  fscanf(f, "%d", &n);
  cout << "\n So dinh: " << n << "\n Ma tran ke: " << endl;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      fscanf(f, "%d", &A[i][j]);
      cout << A[i][j] << " ";
    }
    cout << endl;
  }
  fclose(f);
}

// Khoi tao chua xet
void KhoiTao_ChuaXet()
{
  for (int i = 0; i < max; i++)
    chuaXet[i] = 1;
}

// thuat toan DFS
void DFS(int u)
{
  // xet dinh u
  chuaXet[u] = 0;
  cout << u << "->";
  for (int v = 0; v < n; v++)
    if (chuaXet[v] == 1 && A[u][v] == 1)
    {
      DFS(v);
    }
}

// thuat toan BFS

void BFS(int u)
{
  int queue[max], dau = 0, cuoi = 0;
  for (int i = 0; i < max; i++)
    queue[i] = 0;
  queue[cuoi] = u;
  chuaXet[u] = 0;
  cout << u << "->";

  while (dau >= cuoi)
  {
    int p = queue[cuoi];
    cuoi++;
    for (int v = 0; v < n; v++)
      if (chuaXet[v] == 1 && A[p][v] == 1)
      {
        dau++;
        queue[dau] = v;
        chuaXet[v] = 0;
        cout << v << "->";
      }
  }
}

// Kiem tra chuaXet
int KT_ChuaXet()
{
  for (int i = 0; i < n; i++)
    if (chuaXet[i] == 1)
      return i;
  return -1;
}

// Dem so thanh phan lien thong

int DemSLT()
{
  int slt = 0;
  KhoiTao_ChuaXet();
  while (KT_ChuaXet() != -1)
  {
    int i = KT_ChuaXet();
    DFS(i);
    slt++;
  }
  cout << "\n So lien thong: " << slt;
  return slt;
}

// tim bac cac dinh
int Deg(int i)
{
  int deg = 0;
  for (int j = 0; j < n; j++)
  {
    deg += A[i][j];
  }
  return deg;
}

// Kiem tra do thi Euler

void Test_Euler()
{
  if (DemSLT() == 1)
  {
    // tim bac cua do thi
    int soDinhLe = 0;
    for (int i = 0; i < n; i++)
      if (Deg(i) % 2 != 0)
        soDinhLe++;
    if (soDinhLe == 0)
      cout << "\n Do thi la Euler";
    else if (soDinhLe == 2)
      cout << "\n Do thi la nua Euler";
    else
      cout << "\n Do thi khong phai Euler";
  }
  else
    cout << "\n Do thi khong la Euler";
}

// ham chinh

int main()
{
  // doc ma tran
  Doc_File(A, n);
  // Duyet do thi DFS
  KhoiTao_ChuaXet();
  cout << "\n Duyet do thi DFS: ";
  DFS(0);
  // Duyet do thi BFS
  KhoiTao_ChuaXet();
  cout << "\n Duyet do thi BFS: ";
  BFS(0);

  // Dem so lien thong
  DemSLT();

  // Kiem tra Euler
  Test_Euler();
  return 0;
}

Kết quả

Do thi lien thong

Bạn thấy bài viết này như thế nào?: 
Average: 8.3 (3 votes)
Ảnh của Khanh Hoang

Khanh Hoang - Kenn

Kenn is a user experience designer and front end developer who enjoys creating beautiful and usable web and mobile experiences.

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

 
Android

Tương lai của Adobe và sự thất bại của Flash

Một kịch bản khó có thể tưởng tượng là Adobe đã từ bỏ cung cấp Flash Player dành cho các thiết bị di động. Vừa qua, Adobe đã lặng lẽ gỡ bỏ hoàn toàn ứng dụng Flash trên Google Play Store. Đây là một dấu hiệu khẳng định Flash đã thừa nhận thất bại và chính thức bị “khai tử”.

Xu hướng marketing trên các thiết bị di động

Xu hướng marketing trên các thiết bị di động

Thiết bị di động giờ đây không đơn thuần là một phương tiện thông tin-giải trí, nó đã trở thành một kênh bán hàng hiệu quả.

Bài 5:Học sinh lập trình Scratch - Làm quen với biến

Bài 5:Học sinh lập trình Scratch - Làm quen với biến

Bạn đã làm được hai trò chơi: “Mèo nhí diễu hành” và “Dơi bắt chuột, chuột ăn chuối”. Bạn nên hướng dẫn cho bé tự làm từ đầu thật thạo hai trò chơi đó trước khi chuyển qua bước tiếp theo

Tomdesgin.vn

 

Drupal Services