C++: Lý thuyết đồ thị với C++


Đăng ký nhận thông báo về những video mới nhất

Bài viết này sẽ hướng dẫn bạn sử dụng C/C++ để giải quyết một số bài toán lý thuyết đồ thị.

Lưu ý: Các file đầu vào bạn tự tạo và đưa dữ liệu.

Sau đây là một số thuật toán xuất hiện trong bài viết:

  1. Bài toán 1: Tìm đỉnh có bậc cao nhất, bậc nhỏ nhẩt. Tính tổng bậc của đồ thị. Đếm số đỉnh bậc chẵn và bậc lẻ. . .
  2. Bài toán 2: Kiểm tra tính liên thông của một đồ thị vô hướng.
  3. Bài toán 3: Tìm số thành phần liên thông.
  4. Bài toán 4: Tìm kiếm theo chiều sâu.
  5. Bài toán 5: Tìm đường đi Euler.
  6. Bài toán 6: Bài toán du lịch ( tìm kiếm theo chiều sâu).
  7. Bài toán 7: Thuật toán DIJKSTRA tìm đường đi ngắn nhất.

BÀI TOÁN 1:

Viết chương trình tìm bậc cao nhất của đỉnh trong đồ thị với đồ thị vô hướng A[i,j] với A[i,j]=1 nếu có đường đi từ i đến j và ngược lại A[i,j] = 0 nếu không có đường đi từ i đến j.

YÊU CẦU XỬ LÝ:

a) Tìm đỉnh có bậc cao nhất.

a) Tìm bậc nhỏ nhẩt của đỉnh.

c) Tìm đỉnh có bậc nhỏ nhất.

d) Tính tổng bậc của đồ thị.

e) Đếm số đỉnh bậc chẵn và bậc lẻ.

CHƯƠNG TRÌNH MẪU:

#include<stdio.h>
#include<conio.h>
#include<iostream>
#include"limits.h"
#include"values.h"
#define max 50

int a[max][max];
int Bac,max1,min=INT_MAX,Tong;

int BacLonNhat(int &n){
  for(int i=0; i<n; i++){
    Bac=0;
    for(int j=0; j<n; j++)
      if(a[i][j]>0)
        Bac++;
    if(Bac>max1)
      max1 =Bac;
  }
  printf("\n Bac lon nhat: %d",max1);
  return max1;
}

int BacNhoNhat(int &n){
  for(int i=0; i<n; i++){
    Bac=0;
    for(int j=0; j<n; j++)
      if(a[i][j]>0)
        Bac++;
    if(Bacmin =Bac;
  }
  printf("\n Bac nho nhat: %d",min);
  return min;
}

int TongBac(int &n){
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      if(a[i][j]>0)
        Tong++;
  printf("\nTong cac dinh:%d",Tong);
  return Tong;
}

void DinhBacNhoNhat(int &n){
  FILE*g=fopen("output.txt","w");
  int min=BacNhoNhat(n),Bac;
  for(int i = 0; i<n; i++){
    Bac = 0;
    for(int j = 0; j<n; j++)
      if(a[i][j]>0)
        Bac++;
    if(Bac == min)
      printf("\nDinh Bac Nho Nhat: %d",i+1);
  }
}

void DinhBacLonNhat(int &n){
  int max1=BacLonNhat(n),Bac;
  for(int i = 0; i<n; i++){
    Bac = 0;
    for(int j = 0; j<n; j++)
        if(a[i][j]>0)
          Bac++;
    if(Bac == max1)
      printf("\nDinh Bac Lon Nhat: %d",i+1);
  }
}

void DinhBacChan(int &n){
  int Bac,Tong=0;
  printf("\n Cac dinh bac chan:");
  for(int i=0; i<n; i++){
    Bac=0;
    for(int j=0; j<n; j++)
      if(a[i][j]>0)
        Bac++;
    if(Bac%2==0){
      printf("%d, ",i+1);
      Tong++;
    }
  }
  printf("\nTong So Dinh Bac Chan: %d",Tong);
}

void DinhBacLe(int &n){
  int Bac,Tong=0;
  printf("\n Cac dinh bac le:");
  for(int i=0; i<n; i++){
    Bac=0;
    for(int j=0; j<n; j++)
      if(a[i][j]>0)
        Bac++;
    if(Bac%2==1){
      printf("%d, ",i+1);
      Tong++;
    }
  }
  printf("\nTong So Dinh Bac Le: %d",Tong);
}

int main(){
  int n;
  FILE*f=fopen("input1.txt","rb");
  fscanf(f,"%d",&n);
  for(int i=0;ifor(int j=0;j{
    fscanf(f,"%d",&a[i][j]);
  }
  printf("DO THI:\n");
  for(int i=0;i{
    for(int j=0;j{
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  fclose(f);
  TongBac(n);
  DinhBacNhoNhat(n);
  DinhBacLonNhat(n);
  DinhBacChan(n);
  DinhBacLe(n);
  getch();

  return 0;
}

BÀI TOÁN 2

Viết chương trình kiểm tra tính liên thông của một đồ thị vô hướng A[i,j] với A[i,j]=1 nếu có đường đi từ i đến j và ngược lại A[i,j] = 0 nếu không có đường đi từ i đến j.

HƯỚNG DẪN THUẬT TOÁN:

Ý tưởng: Sử dụng thuật toán loang, cụ thể như sau:

- Bước 1: Xuất phát từ một đỉnh bất kz của đồ thị. Ta đánh dấu đỉnh xuất phát và chuyển sang bước 2.

- Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A*i,j+ = 1 và j chưa được đánh dấu và chuyển sang bước 3.

- Bước 3: Thực hiện bước 2 cho đến khi không còn thực hiện được nữa chuyển sang bước 4.

- Bước 4: Kiểm tra nếu số đỉnh đánh dấu nhỏ hơn n (hay tồn tại ít nhất một đỉnh chưa được đánh dấu) đồ thị sẽ không liên thông và ngược lại đồ thị liên thông.

CHƯƠNG TRÌNH MẪU:

#include<stdio.h>
#include<conio.h>
#include<iostream>
#include"limits.h"
#include"values.h"
#define max 50
int a[max][max];

char LienThong(int &n){
  char DanhDau[n];
  char ThanhCong;
  int Dem=0;
  for(int i=0;iDanhDau[i] = 0;
    DanhDau[0] = 1;
  Dem++;
  do{
    ThanhCong =1;
    for(int i=0; i<n; i++)
      if(DanhDau[i]==1){
        for(int j = 0; j<n; j++)
          if (DanhDau[j] == 0 && a[i][j] > 0){
            DanhDau[j] = 1;
            ThanhCong =0;
            Dem++;
            if(Dem == n)
              return 1;
          }
      }
  }while (ThanhCong == 0);return 0;
}

int main(){
  int n;
  FILE* f=fopen("input2.txt","rb"); //input1-input2
  fscanf(f,"%d",&n);
  for(int i=0;ifor(int j=0;j{
    fscanf(f,"%d",&a[i][j]);
  }
  printf("DO THI:\n");
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  fclose(f);
  if(LienThong(n)==1)
    printf("DO THI LIEN THONG :)");
  else
    printf("do thi KHONG lien thong :(");
  
  return 0;
}

BÀI TOÁN 3

Viết chương trình đếm số thành phần liên thông của đồ thị vô hướng Anxn với:

- A[i,j] = 1 nếu có đường đi từ i đến j.

- A[i,j] = 0 nếu không có đường đi từ i đến j.

- A[i,j] = A[j,i].

CHƯƠNG TRÌNH MẪU:

#include<bits/stdc++.h>
#include<stdio.h>
#include<conio.h>
#include<iostream>

using namespace std;

#include"limits.h"
#include"values.h"
#define max 50
int a[max][max];

char LienThong(int &n){
  char DanhDau[n];
  char ThanhCong;
  int Dem=0;
  for(int i=0; i<n; i++)
    DanhDau[i] = 0;
  DanhDau[0] = 1;
  Dem++;
  do{
    ThanhCong =1;
    for(int i=0; i<n; i++)
      if(DanhDau[i]==1){
        for(int j = 0; j<n; j++)
          if (DanhDau[j] == 0 && a[i][j] > 0){
            DanhDau[j] = 1;
            ThanhCong =0;
            Dem++;
            if(Dem == n)
              return 1;
          }
      }
  }while (ThanhCong == 0);
  return 0;
}

int TPLienThong(int &n){
  char DanhDau[n];
  char ThanhCong;;
  int Dem=0, i,j, MLT=0;
  for( i = 0; i<n; i++)
    DanhDau[i] = 0;
  do{
    j = 0;
    while(DanhDau[j]==1)
      j++;
    DanhDau[j] = 1;
    Dem++;
    MLT++;
    do{
      ThanhCong =0;
      for(i = 0; i<n; i++)
        if(DanhDau[i]==1)
          for(j = 0; j<n; j++)
            if (DanhDau[j] == 0 && a[i][j] > 0){
              DanhDau[j] = 1;
              ThanhCong =1;
              Dem++;
              if(Dem == n){
                printf("%d",MLT);
                return MLT;
              }
            }
    }while (ThanhCong == 1);
  }while(Dem<n);
  printf("%d",MLT);
  return MLT;
}

int main(){
  int n;
  FILE*f=fopen("input3.txt","rb"); //input1-input2
  fscanf(f,"%d",&n);
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++){
      fscanf(f,"%d",&a[i][j]);
    }
  printf("DO THI:\n");
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  fclose(f);
  if(LienThong(n)==1)
    printf("DO THI LIEN THONG :)");
  else
    printf("do thi KHONG lien thong :(");
  printf("\nSo do thi lien thong:");
  TPLienThong(n);
  getch();
  return 0;
}

BÀI TOÁN 4

Có n thành phố biết rằng đường đi giữa hai các thành phố (nếu có) là đường đi hai chiều.

Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận Anxn trong đó:

a. A*i,j+ = 1 nếu có đường đi từ thành phố i đến thành phố j.

b. A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.

c. A[i,j] = A[j,i].

Hãy xác định mọi đường từ thành phố D đến thành phố C (nếu có).

HƯỚNG DẪN THUẬT TOÁN

Sử dụng kỹ thuật tìm kiếm theo chiều sâu.

HƯỚNG DẪN CÀI ĐẶT

Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy.

CHƯƠNG TRÌNH MẪU:

#include<stdio.h>
#include<conio.h>
#include<iostream>
#include"limits.h" // xem dong 39, doi ten file input de kiem tra them ma tran khac
#include"values.h" //
#define max 50

int a[max][max],DinhEND,n,Dem=0,D,C,L[max];
char DanhDau[max];

void KhoiTao(){
  for (int i = 0; i<max; i++){
    DanhDau[i] = 0;
    L[i] = 0;
  }
  DanhDau[D] = 1;
  L[0] = D;
}

void InDuongDi(int SoCanh){
  Dem++;
  printf("\n");
  printf("%d",D+1);
  for (int i = 1; i<SoCanh; i++){
    printf("->%d",L[i]+1);
    if(L[i]+1==DinhEND)
      printf("\n");
    }
}

void TimKiem(int SoCanh){
  if(L[SoCanh-1] == C)
    InDuongDi(SoCanh);
  else{
    for(int i = 0; i<SoCanh; i++)
      if( a[L[SoCanh-1]][i]>0 && DanhDau[i] == 0){
        L[SoCanh] = i;
        DanhDau[i] = 1;
        TimKiem(SoCanh+1);
        L[SoCanh] = 0;
        DanhDau[i] = 0;
      }
  }
}

int main(){
  FILE*f=fopen("input4.txt","rb"); //input1-input2
  fscanf(f,"%d%d%d",&n,&D,&C);
  DinhEND=C;
  printf("Ma Tran Lien Ket Tuong Ung:");
  printf(" %d - %d",D,C);
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++){
      fscanf(f,"%d",&a[i][j]);
    }
  printf("\nDO THI:\n");
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  fclose(f);
  D--;
  C--;
  KhoiTao();
  printf("Duong di tu %d den %d: ",D+1,C+1);
  TimKiem(1);
  if(Dem==0)
    printf("KHONG CO...enter de thoat di ");

  return 0;
}

BÀI TOÁN 5

Một lưới giao thông hai chiều giữa n địa điểm được cho bởi ma trận A*i,j+ trong đó A*i,j+=1 nếu có đường đi từ i đến j, còn A*i,j+ = 0 trong trường hợp ngược lại.

Một người đưa thơ cần đi qua tất cả các con đường này để phát thơ, mỗi đường chỉ qua một lần. Hãy xác định một lộ trình của người đưa thơ này (có thể tồn tại nhiều lộ trình khác nhau) hay thông báo không tồn tại đường như vậy.

HƯỚNG DẪN THUẬT TOÁN:

Bài toán 5 chính là bài toán tìm đường đi Euler. Điều kiện để có đường đi Euler là:

- Đồ thị liên thông.

- Đồ thị có không quá 2 đỉnh bậc lẻ. Nếu có 2 đỉnh bậc lẻ thì đỉnh xuất phát tìm đường đi phải là đỉnh bậc lẻ.

Ý TƯỞNG THUẬT TOÁN:

Sử dụng kỹ thuật xoá cạnh. Nghĩa là, khi ta đi qua bất kz cạnh nào ta phải xoá cạnh tương ứng bằng cách gán trọng số đường đi của cạnh mới đi qua bằng 0. Thuật toán kết thúc khi ta đi qua tất cả các cạnh của đồ thị khi đó ma trận trận liên kết của đồ thị bằng 0.

Lưu ý: Đây là giải thuật đệ quy.

CHƯƠNG TRÌNH MẪU:

#include<stdio.h>
#include<conio.h>
#include<iostream>
#include"limits.h"
#include"values.h"
#define max 50
int a[max][max];
int L[max],n,XuatPhat=0,Dem=0;
int SoCanh=0;

void InDuongDi() {
  Dem++;
  printf("\n%d",XuatPhat+1);
  for (int i = 1; i<=n; i++)
    printf(" -> %d",L[i]+1);
}

void TimKiem(int Canh) {
  /*Tìm cho den khi canh tìm duoc lon hon so canh cua do thi moi xuat duong di*/
  if(Canh > SoCanh && Dem ==0)
    InDuongDi();
  else {
    for(int i = 0; i<Canh; i++)
      if(a[L[Canh-1]][i]>0 && Dem==0){
        L[Canh] = i;
        a[L[Canh-1]][i]=a[i][L[Canh-1]]=0; //Xóa cạnh
        TimKiem(Canh+1); //Tìm đỉnh tiếp theo
        a[L[Canh-1]][i]=a[i][L[Canh-1]]=1; //Phục hồi cạnh
        L[Canh] = 0;
      }
  }
}

int main(){
  int BacDinh;
  FILE*f=fopen("input5.txt","rb");
  fscanf(f,"%d",&n);
  for(int i=0; i<n; i++){
    BacDinh = 0;
    for(int j=0; j<n; j++){
      fscanf(f,"%d",&a[i][j]);
      if(a[i][j] == 1) BacDinh++;
    }
    if(BacDinh%2==1)
      XuatPhat = i;
    SoCanh+=BacDinh;
  }
  SoCanh = SoCanh/2;
  L[0] = XuatPhat;
  printf("DO THI:\n");
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  fclose(f);
  printf("\nDUONG DI EULER:\n");
  TimKiem(1);
  if(Dem==0)
    printf(" k co duong euler -_-");
  return 0;
}

BÀI TOÁN 6

Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n, mỗi thành phố người khách chỉ muốn đi qua chúng một lần. Mạng lưới giao thông giữa n thành phố là hai chiều và được cho bởi ma trận A[i,j] trong đó A*i,j+ =1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại.

Hãy viết chương trình thiết lập cho người khách một lộ trình (có thể tồn tại nhiều lộ trình) hay thông báo không tồn tại lộ trình theo yêu cầu của khách.

HƯỚNG DẪN THUẬT TOÁN

Sử dụng kỹ thuật tìm kiếm theo chiều sâu.

HƯỚNG DẪN CÀI ĐẶT

Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy.

CHƯƠNG TRÌNH MẪU:

#include
#include
#include
#include"limits.h" // xem dong 39, doi ten file input de kiem tra them ma tran
khac
#include"values.h"
#define max 50
int a[max][max];
int L[max],Dem=0,n,D;
char DanhDau[max];

void KhoiTao(){
  for (int i = 0; i<max; i++){
    DanhDau[i] = 0;
    L[i] = 0;
  }
  DanhDau[D] = 1;
  L[0] = D;
}

void InDuongDi(int Dinh){
  Dem++;
  printf("\n%d",D+1);
  for (int i = 1; i<Dinh; i++)
    printf("->%d",L[i]+1);
}

void TimKiem(int Dinh){
  if(Dinh == n && Dem == 0)
    InDuongDi(Dinh);
  else{
    for(int i = 0; i<Dinh; i++)
      if(a[L[Dinh-1]][i]>0 && DanhDau[i] == 0 && Dem==0){
        L[Dinh] = i;
        DanhDau[i] = 1;
        TimKiem(Dinh+1);
        L[Dinh] = 0;
        DanhDau[i] = 0;
      }
  }
}

int main(){
  FILE*f=fopen("input6.txt","rb"); //input1-input2
  fscanf(f,"%d%d",&n,&D);
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++){
      fscanf(f,"%d",&a[i][j]);
    }
  D--;
  printf("DO THI:\n");
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  fclose(f);
  //
  printf("\nDUONG DI NGUOI KHACH:\n");
  TimKiem(1); // input2-TimKiem(0)
  if(Dem==0)
    printf(" k co duong -_-");
  return 0;
}

BÀI TOÁN 7

Có n thành phố biết rằng đường đi giữa các thành phố (nếu có) là đường đi hai chiều.

Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận A*i,j+ trong đó:

- A*i,j+ là độ dài đường đi từ thành phố i đến thành phố j. A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.

- A[i,j] = A[j,i] A[i,j] nguyên, không âm. Hãy xác định đường đi ngắn nhất từ thành phố D đến thành phố C.

HƯỚNG DẪN THUẬT TOÁN

Sử dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất.

CHƯƠNG TRÌNH MẪU:

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

#include"limits.h" // xem dong 39, doi ten file input de kiem tra them ma tran khac
#include"values.h"
#define max 50
int a[max][max];

void Dijkstra(int &n, int D, int C){
  char DanhDau[max],i,j;
  int Nhan[max],Truoc[max],XP,min;
  for( i=0; i<max; i++){
    Nhan[i]=INT_MAX;
    DanhDau[i]=0;
    Truoc[i]=D;
  }
  Nhan[D] = 0;
  DanhDau[D] = 1;
  XP = D;
  while(XP != C){
    for(j=0; j<n; j++)
      if(a[XP][j]>0 && Nhan[j]>a[XP][j]+Nhan[XP] && DanhDau[j]==0){
        Nhan[j] = a[XP][j]+Nhan[XP];
        Truoc[j] = XP;
      }
    min = INT_MAX;
    for(j = 0; j<n; j++)
      if(min>Nhan[j]&& DanhDau[j]==0){
        min = Nhan[j] ;
        XP = j ;
      }
    DanhDau[XP] = 1;
  }
  printf("Duong di ngan nhat la:%d\n",Nhan[C]);
  printf("%d<-%d",C+1,Truoc[C]+1);
  i = Truoc[C];
  while(i!=D){
    i = Truoc[i];
    printf("<-%d",i+1);
  }
}

int main(){
  int D,C,n,Dau,Cuoi;
  FILE*f=fopen("input7.txt","rb"); //input1-input2
  fscanf(f,"%d%d%d",&n,&D,&C);
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++){
      fscanf(f,"%d",&a[i][j]);
    }
  D--;
  C--;
  printf("DO THI:\n");
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  fclose(f);
  Dijkstra(n,D,C);

  return 0;
}

Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!