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: 7.1 (7 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

Filtered HTML

  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Các thẻ HTML được chấp nhận: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Tự động ngắt dòng và đoạn văn.

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

 
An Inside Look at Apple’s New In-Store Pickup Service

An Inside Look at Apple’s New In-Store Pickup Service

A few weeks ago, Apple updated its retail store app with multiple new features. The two that really stood out were the EasyPay self-checkout option and the new in-store pickup service.

Phần 1: Giới thiệu sơ lược, cơ bản WordPress

Phần 1: Giới thiệu sơ lược, cơ bản WordPress

Nếu bạn đã sẵn sàng rồi thì hãy để mình đưa bạn vào tham quan trước về các khái niệm quan trọng về WordPress cũng như những lý do rất tuyệt vời để bạn nên sử dụng nó ngay từ hôm nay.

Hướng dẫn Reloading a View + arguments với Ajax trong Drupal 7

Hướng dẫn Reloading a View + arguments với Ajax trong Drupal 7

If we drill down this file and analyze it, we will understand some of the Views' ajax functionality. Lets take a case and see how we can reuse Views' Ajax.

Công ty diệt chuột T&C

 

Diet con trung