#include <iostream>
#include <time.h>
#include <conio.h>
#include <vector>
#include <queue>
using namespace std;
void search(bool *passed, int unit, int **GM, int n){
vector <int> par;
int i = 0,j = 0;
int *queue=new int[n];
int * d = (int *) calloc(n, sizeof(int));
int count, head;
for (i=0; i<n; i++)
queue[i]=0;
count=0; head=0;
queue[count++]=unit;
passed[unit]=true;
while (head<count){
unit=queue[head++];
//cout << unit << " ";
par.push_back(unit);
for (i=0; i<n; i++)
if (GM[unit][i] && !passed[i]){
queue[count++]=i;
d[i] = d[unit] + 1;
passed[i]=true;
}
}
bool done = false;
int dd = 0;
while (!done){
done = true;
cout << "( ";
for (int i = 0; i<n; ++i){
if (d[i] == dd && passed[i]){
cout << i << ' ';
}
if (d[i] == dd + 1) done = false;
}
cout << ")";
if (!done) cout << " -> ";
++dd;
}
cout << endl;
vector <int> :: iterator r;
cout << "Каркас:" << endl;
for ( r = par.begin(); r < par.end(); r++)
cout << *r << " ";
cout << endl;
free(d);
delete []queue;
}
void Shir()
{
cout << "Поиск в ширину:" << endl;
int n;
cout << "Введите количество вершин: " ;
cin >> n;
cout << endl;
bool *vis=new bool[n];
int **GM;
int start,i,j;
srand(time(NULL));
GM = (int**)malloc(n*sizeof(int));
for ( i = 0; i < n ; i ++)
GM[i] = (int*)calloc(n,sizeof(int));
for( i = 0; i < n; i++)
for ( j = 0; j < n; j++)
GM[i][j] = rand()%2;
for ( i = 0; i < n ; i++)
for ( j = 0; j <n; j++){
GM[i][j] = GM[j][i];
GM[i][i] = 0;
}
cout<<"Матрица: "<<endl;
for (i=0; i<n; i++){
vis[i]=false;
for (j=0; j<n; j++)
cout << " " << GM[i][j];
cout<<endl;
}
cout<<"Введите стартовую вершину: ";
cin>>start;
cout<<"Путь: " << endl;
search(vis, start, GM, n);
// bfs(start,GM,vis,n);
delete []vis;
for ( i = 0; i < n; i++)
free(GM[i]);
free(GM);
}
void Gsearch(int st, int **graph, bool *visited, int n){
int r;
visited[st]=true;
for (r=0; r<n; r++)
if ((graph[st][r]) && (!visited[r])){
cout << st << " -> " << r << endl;
Gsearch(r, graph, visited, n);
}
}
void Glub(){
cout << "Поиск в глубину:" << endl;
int n=5;
cout << "Введите количество вершин: " ;
cin >> n;
cout << endl;
int i, j,start;
bool *visited=new bool[n];
int **graph;
int **tree;
srand(time(NULL));
graph = (int**)malloc(n*sizeof(int));
tree = (int**)malloc(n*sizeof(int));
for ( i = 0; i < n ; i ++)
graph[i] = (int*)calloc(n,sizeof(int));
tree[i] = (int*)calloc(n,sizeof(int));
for( i = 0; i < n; i++)
for ( j = 0; j < n; j++)
graph[i][j] = rand()%2;
for( i = 0; i < n; i++)
for ( j = 0; j < n; j++){
graph[i][j] = graph[j][i];
graph[i][i] = 0;
}
cout<<"Матрица: "<<endl;
for (i=0; i<n; i++){
visited[i]=false;
for (j=0; j<n; j++)
cout<<" "<<graph[i][j];
cout<<endl;
}
cout<<"Введите стартовую вершину: "; cin>>start;
cout<<"Каркас:" << endl;
Gsearch(start,graph,visited,n);
delete []visited;
}
int main(){
setlocale(LC_ALL, "Rus");
Shir();
Glub();
}