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: 6.9 (12 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

 
Error

Những lỗi thường gặp của Keyword Research

Sau nhiều tháng ngày làm SEO vất vả và cuối cùng thì không đạt được những gì mình mong muốn. Sẽ có nhiều câu hỏi đặt ra, vì sao giá click của tôi quá thấp, vì sao tôi đã ở Top 1 nhưng quá ít visit ?

Làm sao để google index nhanh?

Làm sao để google index nhanh?

Sau đây chúng tôi xin giới thiệu với các bạn cách để robot của các bộ máy tìm kiếm ghé thăm website của bạn thường xuyên ?

Nghề Dựng Phim – “Cây Đũa Phép” Của Ngành Điện Ảnh

Nghề Dựng Phim – “Cây Đũa Phép” Của Ngành Điện Ảnh

Năm 1989, Robert William Paul khởi sướng cho định nghĩa về Nghề Dựng Phim với việc ghép hai cảnh quay trong một bộ phim hài không thoại 38 giây “Come Along, Do!” và bước đầu xây dựng nền tảng cho phim điện ảnh sau này

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

 

Diet con trung