//Bai 1
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<fstream.h>
#define MAX 100
//
int n;
int a[100][100],chuaxet[MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi.txt");
f1>>n;
cout<<"
"<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void matranvohuong(){
int s[MAX][MAX];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
s[i][j]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1){
s[i][j] = s[j][i] = 1;
}
}
}
cout<<"Ma tran ke cua do thi vo huong nen:
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<s[i][j]<<" ";
}
cout<<"
";
}
}
//
void DFS(int u){
cout<<u<<" ";
chuaxet[u] = 0; //dinh u cho la da xet
for(int i=1;i<=n;i++)
if((a[u][i])== 1 && (chuaxet[i]== 1)) //neu co duong tu u den i ma i chua xet
DFS(i); // thi duyet dfs dinh i
}
//
void Duyetdinh_DFS(int u){
for(int i=1;i<=n;i++)
chuaxet[i] = 1; //cho tat ca cac dinh la chua xet
DFS(u); //bat dau duyet DFS tu dinh u
}
//
void bacvohuong(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]==1) a[j][i]=1;
cout<<"
Bac cac dinh cua do thi:
";
for(int i=1;i<=n;i++){
int bac=0;
for(int j=1;j<=n;j++)
bac+=a[i][j];
cout<<"Bac cua dinh "<<i<<" "<<bac<<"
";
}
}
//
int kiemtralienthong(){
for(int i=1;i<=n;i++)
chuaxet[i]=1;
DFS(1);
for(int i=1;i<=n;i++)
if(chuaxet[i]==1) return 0; //sau khi duyet tu 1 dinh ma van con dinh chua duyet thi
return 1; //chung to ko co duong di tu dinh dinh 1 den dinh do
}
//
int kiemtrabacchan(){
for(int i=1;i<=n;i++){
int bac=0;
for(int j=1;j<=n;j++)
bac+=a[i][j];
if(bac%2==1) return 0;
}
return 1;
}
//
void kiemtraEuler(){
if(kiemtralienthong()){
cout<<"
Do thi lien thong !";
if(kiemtrabacchan())
cout<<"
Do thi co chu trinh Euler";
else
cout<<"
Do thi khong co chu trinh Euler do co dinh bac le
";
}
else{
cout<<"
Do thi khong lien thong -> khong co chu trinh Euler";
}
}
//
int main(){
docdulieu();
matranvohuong();
int u;
cout<<"
Nhap u = ";
cin>>u;
cout<<"Duyet DFS tu dinh "<<u<<" : ";
Duyetdinh_DFS(u);
bacvohuong();
kiemtraEuler();
}
//Bai 2
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<fstream.h>
#define MAX 100
#include "queue.cpp""
//
int n;
int a[MAX][MAX],chuaxet[MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi.txt");
f1>>n;
cout<<"
"<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void matranvohuong(){
int s[MAX][MAX];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
s[i][j]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1){
s[i][j] = s[j][i] = 1;
}
}
}
cout<<"Ma tran ke cua do thi vo huong nen:
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<s[i][j]<<" ";
}
cout<<"
";
}
}
//
void Duyetdinh_BFS(int u){
queue q;
Init(&q);
Push(&q,u); //duyet tu dinh u
for(int i=1;i<=n;i++){
chuaxet[i] = 1;
}
while(!IsEmpty(&q)){
int k = Get(&q); //tham phan tu dau tien cua queue
cout<<" "<<k;
chuaxet[k]=0; //gan la da xet
for(int i=1;i<=n;i++){ //duyet ma tran xem k noi voi dinh nao
if(a[k][i]==1 && chuaxet[i]==1){ //neu dinh do chua xet
Push(&q,i); //thi day vao queue
chuaxet[i]=0; //va gan dinh do da xet
}
}
}
}
//
void bacvohuong(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]==1) a[j][i]=1;
cout<<"
Bac cac dinh cua do thi:
";
for(int i=1;i<=n;i++){
int bac=0;
for(int j=1;j<=n;j++)
bac+=a[i][j];
cout<<"Bac cua dinh "<<i<<" "<<bac<<"
";
}
}
//
int kiemtralienthong(){
for(int i=1;i<=n;i++)
chuaxet[i]=1;
Duyetdinh_BFS(1);
for(int i=1;i<=n;i++)
if(chuaxet[i]==1) return 0; //sau khi duyet tu 1 dinh ma van con dinh chua duyet thi
return 1; //chung to ko co duong di tu dinh dinh 1 den dinh do
}
//
int kiemtrabacchan(){
for(int i=1;i<=n;i++){
int bac=0;
for(int j=1;j<=n;j++)
bac+=a[i][j];
if(bac%2==1) return 0;
}
return 1;
}
//
void kiemtraEuler(){
if(kiemtralienthong()){
cout<<"
Do thi lien thong !";
if(kiemtrabacchan())
cout<<"
Do thi co chu trinh Euler";
else
cout<<"
Do thi khong co chu trinh Euler do co dinh bac le
";
}
else{
cout<<"
Do thi khong lien thong -> khong co chu trinh Euler";
}
}
//
int main(){
docdulieu();
matranvohuong();
int u;
cout<<"
Nhap dinh u = ";
cin>>u;
cout<<"
Duyet BFS("<<u<<"): ";
Duyetdinh_BFS(u);
cout<<"
";
kiemtraEuler();
}
//Bai 3
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<fstream.h>
#define MAX 100
#include "queue.cpp""
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX][MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi1.txt");
f1>>n;
cout<<"
"<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void matranvohuong(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
s[i][j]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1){
s[i][j] = s[j][i] = 1;
}
}
}
cout<<"Ma tran ke cua do thi vo huong nen:
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<s[i][j]<<" ";
}
cout<<"
";
}
}
//
void DFS(int u){
cout<<u<<" ";
chuaxet[u] = 0; //dinh u cho la da xet
for(int i=1;i<=n;i++)
if((s[u][i])== 1 && (chuaxet[i]== 1)) //neu co duong tu u den i ma i chua xet
DFS(i); // thi duyet dfs dinh i
}
//
void Duyetdinh_DFS(int u){
for(int i=1;i<=n;i++)
chuaxet[i] = 1; //cho tat ca cac dinh la chua xet
DFS(u); //bat dau duyet DFS tu dinh u
}
//
void bacvao_bacra(){
for(int i=1;i<=n;i++){
int bacvao = 0;
int bacra = 0;
for(int j=1;j<=n;j++){
bacra += a[i][j];
bacvao += a[j][i];
}
cout<<"
Dinh "<<i<<" co bac ra = "<<bacra<<" va co bac vao = "<<bacvao;
}
}
//
int main(){
docdulieu();
matranvohuong();
int u;
cout<<"
Nhap u = ";
cin>>u;
cout<<"Duyet DFS tu dinh "<<u<<" : ";
Duyetdinh_DFS(u);
bacvao_bacra();
}
//Bai 4
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<fstream.h>
#define MAX 100
#include "queue.cpp""
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX][MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi1.txt");
f1>>n;
cout<<"
"<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void matranvohuong(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
s[i][j] = 0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1) s[i][j] = s[j][i] = 1;
}
}
cout<<"Ma tran ke cua do thi vo huong nen:
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<s[i][j]<<" ";
}
cout<<"
";
}
}
//
void Duyetdinh_BFS(int u){
queue q;
Init(&q);
Push(&q,u); //duyet tu dinh u
for(int i=1;i<=n;i++){
chuaxet[i] = 1;
}
while(!IsEmpty(&q)){
int k = Get(&q); //tham phan tu dau tien cua queue
cout<<" "<<k;
chuaxet[k]=0; //gan la da xet
for(int i=1;i<=n;i++){ //duyet ma tran xem k noi voi dinh nao
if(s[k][i]==1 && chuaxet[i]==1){ //neu dinh do chua xet
Push(&q,i); //thi day vao queue
chuaxet[i]=0; //va gan dinh do da xet
}
}
}
}
//
void bacvao_bacra(){
for(int i=1;i<=n;i++){
int bacvao = 0;
int bacra = 0;
for(int j=1;j<=n;j++){
bacra += a[i][j];
bacvao += a[j][i];
}
cout<<"
Dinh "<<i<<" co bac ra = "<<bacra<<" va co bac vao = "<<bacvao;
}
}
//
int main(){
docdulieu();
matranvohuong();
int u;
cout<<"
Nhap dinh u = ";
cin>>u;
cout<<"
Duyet BFS("<<u<<"): ";
Duyetdinh_BFS(u);
cout<<"
";
bacvao_bacra();
}
//Bai 5
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<fstream.h>
#define MAX 100
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX][MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi2.txt");
f1>>n;
cout<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void matranvohuong(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
s[i][j] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j] == 1)
s[i][j] = s[j][i] = 1;
}
}
cout<<"
Ma tran ke cua do thi vo huong nen la:
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<s[i][j]<<" ";
}
cout<<"
";
}
}
//
void DFS(int u){
cout<<u<<" ";
chuaxet[u] = 0; //dinh u cho la da xet
for(int i=1;i<=n;i++)
if((s[u][i])== 1 && (chuaxet[i]== 1)) //neu co duong tu u den i ma i chua xet
DFS(i); // thi duyet dfs dinh i
}
//
void Duyetdinh_DFS(){
int u;
cout<<"
Nhap dinh u = ";
cin>>u;
for(int i=1;i<=n;i++)
chuaxet[i] = 1; //cho tat ca cac dinh la chua xet
DFS(u); //bat dau duyet DFS tu dinh u
}
//
int kiemtralienthong(){
for(int i=1;i<=n;i++)
chuaxet[i]=1;
DFS(1);
for(int i=1;i<=n;i++)
if(chuaxet[i]==1) return 0; //sau khi duyet tu 1 dinh ma van con dinh chua duyet thi
return 1; //chung to ko co duong di tu dinh dinh 1 den dinh do
}
//
void sothanhphanlienthong(){
for(int i=1;i<=n;i++)
chuaxet[i] = 1;
int count = 1;
for(int i=1;i<=n;i++)
if(chuaxet[i]==1){
cout<<"
Thanh phan lien thong thu "<<count<<" :";
DFS(i);
count++;
}
}
//
int main(){
docdulieu();
matranvohuong();
Duyetdinh_DFS();
cout<<"
";
int i = kiemtralienthong();
if(i == 1) cout<<"
Do thi vo huong nen lien thong";
else cout<<"
Do thi vo huong nen khong lien thong";
cout<<"
";
sothanhphanlienthong();
}
//Bai 6
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<fstream.h>
#include "queue.cpp"
#define MAX 100
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX][MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi2.txt");
f1>>n;
cout<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void matranvohuong(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
s[i][j] = 0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(a[i][j]==1) s[i][j] = s[j][i] =1;
}
cout<<"
Ma tran ke cua do thi vo huong nen la:
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<s[i][j]<<" ";
}
cout<<"
";
}
}
//
void BFS(int u){
queue q;
Init(&q);
Push(&q,u);
while(!IsEmpty(&q)){
int k = Get(&q);
cout<<k<<" ";
chuaxet[k] = 0;
for(int i=1;i<=n;i++){
if(s[k][i]==1 && chuaxet[i] == 1){
Push(&q,i);
chuaxet[i] = 0;
}
}
}
}
//
void Duyetdinh_BFS(int u){
for(int i=1;i<=n;i++)
chuaxet[i] = 1;
BFS(u);
}
//
int kiemtralienthong(){
for(int i=1;i<=n;i++){
chuaxet[i] = 1;
}
BFS(1);
for(int i=1;i<=n;i++){
if(chuaxet[i]==1) return 0;
}
return 1;
}
//
void sothanhphanlienthong(){
int k = 1;
for(int i=1;i<=n;i++)
chuaxet[i] = 1;
for(int j=1;j<=n;j++){
if(chuaxet[j]==1){
cout<<"
Thanh phan lien thong thu "<<k<<" :";
BFS(j);
k++;
}
}
}
//
int main(){
docdulieu();
matranvohuong();
int u;
cout<<"
Nhap u = ";
cin>>u;
Duyetdinh_BFS(u);
cout<<"
";
int s = kiemtralienthong();
if(s) cout<<"
Do thi lien thong";
else cout<<"
Do thi ko lien thong";
sothanhphanlienthong();
}
//Bai 7
#include<iostream.h>
#include<conio.h>
#include<fstream.h>
#include<stdlib.h>
#define MAX 100
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi3.txt");
f1>>n;
cout<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
int kiemtramatranke(){
for(int i=1;i<=n;i++)
if(a[i][i] == 1) return 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j] != a[j][i]) return 0;
return 1;
}
//
void DFS(int u){
cout<<u<<" ";
chuaxet[u] = 0;
for(int i=1;i<=n;i++)
if(a[u][i]==1 && chuaxet[i]==1){
DFS(i);
}
}
//
void Duyetdinh_DFS(){
for(int i=1;i<=n;i++){
chuaxet[i]=1;
}
for(int i=1;i<=n;i++){
DFS(i);
cout<<"
";
for(int i=1;i<=n;i++){
chuaxet[i]=1;
}
}
}
//
void kiemtraLTManh(){
int kiemtra=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) chuaxet[j]=1;
cout<<"
DFS("<<i<<")=";
DFS(i);
for(int j=1;j<=n;j++)
if(chuaxet[j]==1)
kiemtra=0;
}
cout<<"
";
if(kiemtra) cout<<"Lien thong manh!";
else cout<<"Do thi khong lien thong manh";
}
//
int main(){
docdulieu();
if(kiemtramatranke()) cout<<"
YES
";
else cout<<"
NO
";
Duyetdinh_DFS();
kiemtraLTManh();
}
//Bai 8
#include<iostream.h>
#include<conio.h>
#include<fstream.h>
#include<stdlib.h>
#include "queue.cpp"
#define MAX 100
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi3.txt");
f1>>n;
cout<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
int kiemtramatranke(){
for(int i=1;i<=n;i++)
if(a[i][i] == 1) return 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j] != a[j][i]) return 0;
return 1;
}
//
void BFS(int u){
queue q;
Init(&q);
chuaxet[u] = 0;
Push(&q,u);
while(!IsEmpty(&q)){
int k = Get(&q);
cout<<k<<" ";
chuaxet[k] = 0;
for(int i=1;i<=n;i++){
if(a[k][i]==1 && chuaxet[i]==1){
Push(&q,i);
chuaxet[i] = 0;
}
}
}
}
//
void Duyetdinh_BFS(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
chuaxet[j]=1;
cout<<"
BFS("<<i<<")=";
BFS(i);
}
}
//
void kiemtraLTManh(){
int kiemtra=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
chuaxet[j]=1;
cout<<"
BFS("<<i<<")=";
BFS(i);
for(int j=1;j<=n;j++)
if(chuaxet[j]==1)
kiemtra=0;
}
cout<<"
";
if(kiemtra) cout<<"Lien thong manh!";
else cout<<"Do thi khong lien thong manh";
}
//
int main(){
docdulieu();
if(kiemtramatranke()) cout<<"
YES";
else cout<<"
NO";
Duyetdinh_BFS();
cout<<"
";
kiemtraLTManh();
}
//Bai 9
#include<iostream.h>
#include<conio.h>
#include<fstream.h>
#include<stdlib.h>
#include "stack.cpp"
#define MAX 100
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi3.txt");
f1>>n;
cout<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void DFS(int u){
cout<<u<<" ";
chuaxet[u] = 0;
for(int i=1;i<=n;i++)
if(a[u][i]==1 && chuaxet[i]==1){
DFS(i);
}
}
//
void Duyetdinh_DFS(){
for(int i=1;i<=n;i++){
chuaxet[i]=1;
}
DFS(1);
}
//
int DoDuong(int DuongDi[], int u, int v){
Stack s;
int p;
for(int i=1 ; i<=n ; i++)
chuaxet[i]=1;
Init(&s);
//Day u vao stack
Push(&s,u);
chuaxet[u]=0;
while(DuongDi[v]==0){
if(IsEmpty(&s)){//Neu stack rong
cout<<"
Khong co duong di tu "<<u<<" toi "<<v<<"
";
return 0;//Khong co duong
}
p=Pop(&s);
for(int i=1 ; i<=n ; i++){
if(a[p][i]==1 && chuaxet[i]){// Neu i la dinh ke voi dinh p va i chua xet
DuongDi[i]=p;
Push(&s,i);
chuaxet[i]=0;
}
}
}
return (1);
}
void TimDuongDi(){
int DuongDi[MAX];//Mang danh dau duong di
for(int i=1 ; i<=n ; i++)
DuongDi[i]=0;
int u,v,k;
cout<<"
TIM DUONG DI TU DINH u TOI DINH v
";
cout<<"
Nhap dinh u= ";
cin>>u;
cout<<"
Nhap dinh v= ";
cin>>v;
if(u==v){
cout<<"
Duong di tu "<<u<<" toi "<<v<<" la:
";
cout<<u;
return;
}
//Khoi tao 1 stack
k= DoDuong(DuongDi,u,v);
if(k==0){
cout<<"
Khong co duong di tu dinh "<<u<<" toi dinh "<<v;
return;
}
// Khoi tao 1 stack
Stack r;
Init(&r);
k=v;
Push(&r,k);
while(k!=u){
k = DuongDi[k];
Push(&r,k);
}
cout<<"
Duong di tu "<<u<<" toi "<<v<<" la:
";
while(!IsEmpty(&r))
cout<<Pop(&r)<<" ";
}
//
int main(){
docdulieu();
cout<<"
Duyet DFS(1) = ";
Duyetdinh_DFS();
TimDuongDi();
/* int u,v;
cout<<"
Nhap u = ";
cin>>u;
cout<<"
Nhap v = ";
cin>>v;
// if(Duong_Di(Duongdi,u,v)) cout<<"
YES";
// else cout<<"
NO";
// TimDuongDi(u,v); */
}
//Bai 10
#include<iostream.h>
#include<conio.h>
#include<fstream.h>
#include<stdlib.h>
#include "stack.cpp"
#define MAX 100
//
int n;
int a[MAX][MAX],chuaxet[MAX];
int s[MAX];
//
void docdulieu(){
ifstream f1;
f1.open("dothi5.txt");
f1>>n;
cout<<n<<"
";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f1>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"
";
}
}
//
void floy(){
int u,v;
cout<<"Nhap u,v: ";
cin>>u;
cin>>v;
int w[100][100];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
w[i][j]=a[i][j];
if(w[i][j]==0) w[i][j]=100;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(w[i][j]>w[i][k]+w[k][j]) w[i][j]=w[i][k]+w[k][j];
cout<<"Do dai duong di ngan nhat la: "<<w[u][v];
}
//
void timduongdi(int u,int v){
Stack s;
Init(&s);
Push(&s,u);
}
int main(){
docdulieu();
floy();
}
Bạn đang đọc truyện trên: Truyen2U.Pro