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: 10 (1 vote)
Ả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.
6 + 1 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Ứng dụng mới của Google+ - Nhận diện khuôn mặt

Ứng dụng mới của Google+ - Nhận diện khuôn mặt

Google đang “tung chiêu” liên tục để cạnh tranh với Facebook. Và một ứng dụng mới nhất của Google khiến người dùng “nức lòng” là “Find My Face” (Hãy tìm khuôn mặt của tôi)

Drupal 7 Form API: Sử dụng #states cho multiple conditionals (AND, OR and XOR)

Drupal 7 Form API: Sử dụng #states cho multiple conditionals (AND, OR and XOR)

If you have a simple, one off case where you have a conditional field and are reluctant to introduce 2-3k lines of code, you can use hook_form_alter() and #states API.

Giới thiệu bình xịt côn trùng Raid Mik 600ml giá rẻ

Giới thiệu bình xịt côn trùng Raid Mik 600ml giá rẻ

Sản phẩm không mùi và không chứa chất độc hại nên hoàn toàn an toàn cho sức khỏe gia đình bạn.

Wordpress Freelancer

 

Wordpress Freelancer