Code C/C++: Thuật toán Prim tìm cây bao trùm tối thiểu

Mô tả bài toán: cho đồ thị vô hướng có trọng số G=(V,E) hãy tìm đường đi sao cho tất cả các đỉnh điều có đường đi với nhau và tổng trọng số của đường đi là nhỏ nhất.
Ý tưởng thuật toán:
Bước 1: xuất phát từ đỉnh k bất kỳ (thông thường chọn đỉnh đầu tiên) chọn một cạnh có trọng số nhỏ nhất liền kề với đỉnh k (min{A[k][j]}j=1..n) ta đánh dấu 2 đỉnh đi qua cạnh đó và số cạnh tìm được là 1. Chuyển sang Bước 2.
Bước 2: tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải có 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu. Nghĩa là, ta tìm min{A[i][j]} j=1..n, i=1..n sao cho i đánh dấu và j chưa đánh dấu để tránh trường hợp tạo thành chu trình con. Ta tăng số cạnh tìm được lên 1 và chuyển sang Bước 3.
Bước 3: nếu số cạnh tìm được bằng n-1 kết thúc thuật toán, ngược lại quay về Bước 2.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: lưu trong tập tin Bai7.inp
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng i+1 (1<=i<=n) lưu ma trận kề của đồ thị với n số A[i,1], A[i,2],…, A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: lưu trong file Bai7.out
-  Dòng đầu ghi trọng số nhỏ nhất của cây bao trùm.
-  Các dòng còn lại lưu đường đi giữa đỉnh i nối với đỉnh j.
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <values.h>
#define max 100
#define FileInt "Bai7.inp"
#define FileOut "Bai7.out"
typedef struct Egde{
int x,y;
}; 
//đọc dữ liệu từ tập tin
void Doc_File(int A[max][max],int &n) {
FILE*f = fopen(FileInt,”rb”);
fscanf(f,”%d”,&n);
for(int i =0;i<n;i++) {
for(int j =0;j<n;j++) {
fscanf(f,”%d”,&A[i][j]);
}
}
fclose(f);
}
//ghi dữ liệu ra tập tin
void Ghi_File(Egde L[max],int n,int Sum) {
FILE*f = fopen(FileOut,"wb");
fprintf(f,"%d\n",Sum);
for(int i =0; i<n-1; i++)
fprintf(f,"%d -%d\n",L[i].x+1,L[i].y+1);
fclose(f);
}
//thuật toán Prim
void Prim(int A[max][max], int n) {
char D[max];
Egde L[max];
int min = MAXINT, Dem = 0, Sum = 0;
for(int i=0; i<n; i++)
D[i]=0;
for(int j=1; j<n; j++)
if(min>A[0][j] && A[0][j]!=0){
min = A[0][j];
L[0].y = j;
}
L[0].x = 0;
D[0] = 1;
D[L[0].y] = 1;
Sum+=min;
Dem++;
do {
min = MAXINT;
for( i=0; i<n; i++)
if(D[i]==1)
for( j=0; j<n; j++)
if(A[i][j]>0 && min>A[i][j] && D[j]==0){
min = A[i][j]; 
L[Dem].x = i;
L[Dem].y = j;
}
Sum+=min;
D[L[Dem].y] = 1;
Dem++;
} while(Dem<n-1);
Ghi_File(L,n,Sum);
}
//chương trình chính
void main() {
int A[max][max],n;
Doc_File(A,n);
Prim(A,n);

}
Tags: Kỹ thuật lập trình, toán rời rạc, c, c++, prim, cây khung

More about →

Code C/C++: Thuật toán Dijkstra tìm đường đi ngắn nhất

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định đường đi ngắn nhất từ đỉnh D tới đỉnh C của đồ thị G.
Ý tưởng thuật toán: sử dụng thuật toán Dijkstra.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: đồ thị đã liên thông và cho trong tập tin Bai6.inp. 
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng thứ hai lưu đỉnh D và đỉnh C.
-  Dòng i+2 (1<=i<=n) chứa n số A[i,1], A[i,2],…, A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: xuất ra màn hình  đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100
#define FileIn "Bai6.inp"
void Doc_File(int A[max][max], int &n, int &D, int &C) {
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C);
cout<<"Ma Tran Lien Ket Tuong Ung.\n";
cout<<D<<" "<<C<<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);
D--; C--;
}
void Dijkstra(int A[max][max], int n, int D, int C) {
char DanhDau[max];
int Nhan[max], Truoc[max], XP, min;
for(int i=0; i<n; i++){
Nhan[i] = MAXINT;
DanhDau[i] = 0;
Truoc[i] = D;
}
Nhan[D] = 0;
DanhDau[D] = 1;
XP = D;
while(XP != C){
for(int 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 = MAXINT;
for(j = 0; j<n; j++)
if(min>Nhan[j]&& DanhDau[j]==0){
min = Nhan[j];
XP = j;
}
DanhDau[XP] = 1;
}
cout<<"Duong Di Ngan Nhat La:"<<Nhan[C]<<endl;
cout<<C+1<<" <-"<<Truoc[C]+1;
i = Truoc[C];
while(i!=D){
i = Truoc[i];
cout<<" <-"<<i+1;
}
}
void main() {
int A[max][max],n,Dau,Cuoi;



Doc_File(A,n,Dau,Cuoi);
Dijkstra(A,n,Dau,Cuoi);
getch();

} 
Kết quả chạy chương trình:

Tags: kỹ thuật lập trình, c, c++, toán rời rạc, đồ thị, tìm đường đi, Dijkstra.

More about →

Code C/C++: Tìm đường đi Euler của đồ thị (bài toán tìm đường đi)

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần.
Ý tưởng thuật toán:sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: cho trong tập tin Bai5.inp
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng i+1 (1<=i<=n) chứa n số A[i,1], A[i,2],…, A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: in ra màn hình đường đi qua tất cả các cạnh (nếu có)
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Bai5.inp"
int Dem = 0, SoCanh=0;  
int *L;    
int **A,n;
int XuatPhat=0;   
void Doc_File() {
int BacDinh;
FILE*f = fopen(Filename,"rb");
fscanf(f,"%d",&n);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<n<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
BacDinh = 0;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" "; 
if(A[i][j] == 1)
BacDinh++;
}
if(BacDinh%2==1)
XuatPhat = i;    
SoCanh+=BacDinh;
cout<<endl;
}
fclose(f);
SoCanh = SoCanh/2;      
L = new int [SoCanh+1]; 
L[0] = XuatPhat;
}
void InDuongDi() {
Dem++;
cout<<endl<<XuatPhat+1;
for (int i = 1; i<=SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int Canh) {
if(Canh > SoCanh)     
InDuongDi();
else {
for(int i = 0; i<n; i++)
if( A[L[Canh-1]][i]>0){
L[Canh] = i;
A[L[Canh-1]][i]=A[i][L[Canh-1]]=0;  
Try(Canh+1);       
A[L[Canh-1]][i]=A[i][L[Canh-1]]=1;  
L[Canh] = 0;
}
}
}
void main() {
Doc_File();
cout<<"\nDUONG DI";
Try(1);
if(Dem==0)
cout<<" KHONG CO";
delete*A,L;
getch();

} 
Kết quả chạy chương trình:

Tags: Kỹ thuật lập trình, toán rời rạc, c, c++, euler, đồ thị, tìm đường đi

More about →

Code C/C++: Đường đi Hamilton (bài toán đồ thị)

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh xuất phát đi qua tất cả các đỉnh mỗi đỉnh chỉ qua duy nhất 1 lần.
Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách đánh dấu đỉnh đã đi qua trong quá trình tìm kiếm.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: cho trong tập tin Bai4.inp
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng 2 ghi đỉnh xuất phát.
-  Dòng i+2 (1<=i<=n) chứa n số A[i,1], A[i,2],…, A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: in ra màn hình đường đi qua tất cả các đỉnh (nếu có).

Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai4.inp"
intDem = 0;     
int *L;      
char  *DanhDau;  
int**A,n,D;
//Đọc dữ liệu từ tập tin theo yêu cầu bài toán
void Doc_File() {
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d",&n,&D);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--;
}
//Khởi tạo dữ liệu ban đầu cho bài toán
void KhoiTao() {
DanhDau = new char [n];
L = new int [n];
for (int i = 0; i<n; i++) {
DanhDau[i] =0;  
L[i] = 0;
}
DanhDau[D] = 1;    
L[0] = D;
}
//Xuất đường đi ra màn hình
void InDuongDi(int Dinh) {
Dem++;
cout<<endl<<D+1;
for (int i = 1; i<Dinh; i++)
cout<<" -> "<<L[i]+1;
}
//Tìm kiếm đường đi
void Try(int Dinh){
if(Dinh == n) 
InDuongDi(Dinh);
else {
for(int i = 0; i<n; i++)
if( A[L[Dinh-1]][i]>0 && DanhDau[i] == 0){
L[Dinh] = i;
DanhDau[i] = 1;  
Try(Dinh+1);   
L[Dinh] = 0;
DanhDau[i] = 0; 
}
}
}
//Chương trình chính
void main() {
clrscr();
Doc_File();
KhoiTao();
cout<<"Duong di";
Try(1);
if(Dem==0)
cout<<" khong co.";
delete*A,DanhDau,L;
getch();

}
Kết quả chạy chương trình:

Tags: Kỹ thuật lập trình, c, c++, pascal, java, đồ thị, hamilton, tìm đường đi

More about →

Code C/C++: Tìm mọi đường đi từ giữa hai đỉnh của đồ thị

Tìm mọi đường đi từ giữa hai đỉnh
Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh D tới đỉnh C của đồ thị G.
Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: đồ thị liên thông và cho trong tập tin Bai3.inp 
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng thứ hai lưu đỉnh D và đỉnh C.
-  Dòng i+2 (1<=i<=n) chứa n số A[i,1], A[i,2],…, A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra:  Xuất ra màn hình mọi đường đi từ đỉnh D đến C hay thông báo không tồn 
tại đường đi từ D đến C.
Mô tả:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai1a.inp"
intDem = 0;    
int *L;     
char  *DanhDau; 
int **A,n,D,C;
//Đọc dữ liệu từ tập tin
void Doc_File() { 
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C); 
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--; 
C--;
}
//Khởi tạo các biến ban đầu
void KhoiTao() {
DanhDau = new char [n];
L = new int [n];
for (int i = 0; i<n; i++) {
DanhDau[i] = 0;
L[i] = 0;
}
DanhDau[D] = 1;    
L[0] = D;      
}
void InDuongDi(int SoCanh) {
Dem++;
cout<<endl<<D+1;
for (int i = 1; i<SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int SoCanh) {
if(L[SoCanh-1] == C)    
InDuongDi(SoCanh);
else {
for(int i = 0; i<n; i++)
if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0 ){
L[SoCanh] = i;  
DanhDau[i] = 1; 
Try(SoCanh+1); 
L[SoCanh] = 0;
DanhDau[i]= 0;  
}
}
}
void main() {
Doc_File();
KhoiTao();
cout<<"Duong di tu "<<D+1<<" den "<<C+1;
Try(1);
if(Dem==0)
cout<<" khong co duong di";
delete*A,DanhDau,L;
getch();

}
Kết quả chạy chương trình:

Từ khóa: đường đi, đồ thị, đỉnh, c, c++, kỹ thuật lập trình, toán rời rạc, liên thông, tìm đường đi giữa 2 đỉnh của đồ thị

More about →

Code C/C++: Đếm số thành phần liên thông của đồ thị

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy đếm số thành phần liên thông của đồ thị G.
Ý tưởng thuật toán:
Bước 0: khởi tạo số thành phần liên thông bằng 0.
Bước 1: xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông lên 1 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: nếu số đỉnh đánh dấu bằng n kết thúc thuật toán, ngược lại quay về Bước 1.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: cho trong tập tin Bai2.inp
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100).
-  Dòng i+1 ( 1<=i<=n ) chứa n số A[i,1], A[i,2],…, A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: xuất ra màn hình s ố thành phần liên thông của đồ thị.
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define TenFile "Bai2.inp"
//Đọc dữ liệu từ file Bai2.inp
void Doc_File(int **A,int &n)  {
FILE*f = fopen(TenFile,"rb");
fscanf(f,"%d",&n);
*A = new int [n];
cout<<"Ma Tran Lien Ket Cua Do Thi";
for(int i =0;i<n;i++) {
A[i] = new int [n];
cout<<endl;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<" "<<A[i][j];
}
}
fclose(f);
}
//Hàm trả về số thành phần liên thông của đồ thị
int TPLien_Thong(int **A, int n){
char*DanhDau = new char [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) return MLT;
}
}while (ThanhCong == 1);
} while(Dem<n);     
return MLT;
}
//Chương trình chính
void main(){
clrscr();
int **A,n;
Doc_File(A,n);
cout<<"\nThanh phan lien thong: "<<TPLien_Thong(A,n);
delete *A;
getch();
}
Kết quả chạy chương trình:

Từ khóa: c, c++, toán rời rạc, liên thông, đồ thị, kỹ thuật lập trình, giải thuật, đếm thành phần liên thông của đồ thị

More about →

Code C/C++: Xét tính liên thông của đồ thị

Xét tính liên thông của đồ thị
Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy kiểm tra tính liên thông của đồ thị G.
Ý tưởng thuật toán:
Bước 1: xuất phát từ một đỉnh bất kỳ 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.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: cho trong tập tin Bai1.inp
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100).
-  Dòng i+1 ( 1<=i<=n ) chứa n số A[i,1], A[i,2],…,A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: thông báo kết quả ra màn hình ”DO THI LIEN THONG” hay “ DO THI KHONG LIEN THONG”.

Cài đặt chương trình:
#include<math.h>
#include<iostream>
#include<conio.h>
#include<stdio.h>
#define tenfile "bai1.txt"
using namespace std;
//Hàm đọc file
void Doc_File(int **A,int &n)  {
FILE *f = fopen(tenfile,"rb");
fscanf(f,"%d",&n);
*A = new int [n];
cout<<"Ma Tran Lien Ket Cua Do Thi";
for(int i =0;i<n;i++) {
A[i] = new int [n];
cout<<endl;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<" "<<A[i][j];
}
}
fclose(f);
}
//kiem tra tinh lien thong neu lien thong tra ve gia tri 1 nguoc lai tra ve gia tri 0
char Lien_Thong(int **A,int n){
char *DanhDau = new char [n];
char ThanhCong;
int Dem=0;
for(int i = 0; i<n; i++)    //Khoi tao moi dinh chua danh dau
DanhDau[i] = 0;
DanhDau[0] = 1;    //danh dau dinh dau
Dem++;      //dem so dinh duoc danh dau
do {
ThanhCong =1;  //khong con kha nang loang
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;  //con kha nang loang
Dem++;
if(Dem == n) 
return 1; 
}
}
}while (ThanhCong == 0);  //lap lai cho den khi khong con kha nang loan
return 0;
}
//Chuong trinh chinh
int main(){
int **A,n;
Doc_File(A,n);
if (Lien_Thong(A,n)==1)
cout<<"\nDO THI LIEN THONG";
else 
cout<<"\nDO THI KHONG LIEN THONG";
delete *A;
getch();
return 0;

}
Kết quả chạy chương trình:

Từ khóa: Đồ thị, liên thông, graphics, toán rời rạc, kỹ thuật lập trình, c, c++

More about →