include iostream include time include conio include vector include que

#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();
}