DFS / BFS / Euler trên ma trận kề

Cho ma trận kề:

8 // số đỉnh (the number of vertex)
0 1 0 0 0 0 1 1
1 0 0 1 0 0 0 0
0 0 0 0 1 0 1 1
0 1 0 0 1 0 0 0
0 0 1 1 0 1 1 0
0 0 0 0 1 0 1 0
1 0 1 0 1 1 0 0
1 0 1 0 0 0 0 0

……….. Simple solution for beginner:

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define FI "MTK.INP"
#define FO "DFS.OUT"
#define MAX 100
ifstream fi;
ofstream fo;
int n;
vector<vector<int> > MTK;
vector<bool> visited;
void DocFile(){
 fi.open(FI);
 fi >> n;
 visited.resize(n);
 MTK.resize(n);
 for(int i=0; i<n; i++){
 for(int j=0; j<n; j++){
 int temp;
 fi >> temp;
 MTK[i].push_back(temp);
 }
 }
 fi.close();
}
void InitUnvisited(){
 for(int i=0; i<visited.size(); i++){
 visited[i] = false;
 }
}
void DFS(int u){
 visited[u] = true;
 // cout << u << "-> ";
 for(int i=0; i<n; i++){
 if(visited[i] == false && MTK[u][i] == 1){
 DFS(i);
 }
 }
}
int KiemTraChuaXet(){
 for (int i=0;i<n;i++)
 if (visited[i]==false) return i;
 return -1;
}
int DemThanhPhanLienThong(){
 int slt = 0;
 InitUnvisited();
 while(KiemTraChuaXet()!=-1){
 int i = KiemTraChuaXet();
 DFS(i);
 slt++;
 }
 cout << slt;
 return slt;
}
int BacDinh(int i){
 int bac = 0;
 for(int j=0; j<n; j++){
 bac += MTK[i][j];
 }
 return bac;
}
// 
// void XuatFile(){
// fo.open(FO);
// 
// for(int i=0; i<MTK.size(); i++){
// for(int j=0; j<MTK.size(); j++){
// fo << MTK[i][j] << " ";
// }
// fo << endl;
// }
// fo.close();
// }
// 
void isEuler(){
 if(DemThanhPhanLienThong() == 1){
 int sodinhle = 0;
 for(int i=0; i<n; i++){
 if(BacDinh(i) % 2 !=0){
 sodinhle++;
 }
 }
 if(sodinhle == 0){
 cout << "la Euler";
 }
 else{
 if(sodinhle == 2){
 cout << "nua euler";
 }
 else{ cout << "khong phai euler";}
 }
 }
 else { cout << "no";}
}
void BFS(int u){
 int queue[MAX], dau = 0, cuoi = 0;
 InitUnvisited();
 for(int i=0; i<MAX; i++){
 queue[i] = 0;
 }
 queue[cuoi] = u;
 visited[u] = true;
 cout << u << "->";
 while(dau >= cuoi){
 int p = queue[cuoi];
 cuoi++;
 for(int i=0; i<n; i++){
 if(visited[i] == false && MTK[p][i] == 1){
 dau++;
 queue[dau] = i;
 visited[i] = true;
 cout << i << "->";
 }
 }
}
}
int main()
{
 DocFile();
 InitUnvisited();
 DFS(0);
 //DemThanhPhanLienThong();
 // XuatFile();
 isEuler();
 BFS(0);
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s