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.
12 + 8 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

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

 
Yandex

Công cụ tìm kiếm Yandex số 1 ở Nga

Sau giờ làm việc buổi chiều, tôi  ngồi theo dõi mấy Crawler và Spider đang Index site, thấy có Yandex.ru

Watchguard, IronPort

Giải pháp Bảo mật với sản phẩm của Watchguard và IronPort

Theo Báo cáo Thương mại điện tử (TMĐT) Việt Nam 2011 vừa được Cục TMĐT và CNTT - Bộ Công Thương công bố, chỉ có 40% doanh nghiệp quan tâm tới việc bảo vệ thông tin cá nhân.

Hướng dẫn upgrading lên Drupal 8 - client bắt mắt

Hướng dẫn upgrading lên Drupal 8 - client bắt mắt

Having helped create the original Drupal 6 site for NAMA in 2008, it’s been a rewarding experience re-architecting it in Drupal 8 (beta).

Wordpress Freelancer

 

Wordpress Freelancer