task_obhod_v_shirinu.cpp

#include <iostream>
#include <vector>
using namespace std;

struct stack {
	int inf;//сам элемент
	stack* next;//стек поменьше
};
//для решения задачи будем заталкивать в стек нужное слово, а затем выведем, стерев сам стек
//далее об этом подробнее
void push(stack*& h, int x) {//функция добавления нового элемента в стек
	stack* r = new stack;//раз стек, очевидно, после добавления станет больше, то нам нужен будет уже новый стек
	r->inf = x;//элементу нового стека мы присваиваем значение добавляемого элемента
	r->next = h;//а новый стек пусть будет ссылаться на исходный
	h = r;//и меняем местами кто на кого ссылается
}
int pop(stack*& h) {//функция удаления элемента из стека, возвращающая удаляемый элемент 
	int i = h->inf;//для сохранения элемента запишем его в новую переменную
	stack* p = h;//для удаления нам нужно будет удалить сам стек, содержащий удаляемый элемент 
	h = h->next;//но, чтобы не потерять весь основной стек нам нужно переназначить ссылку предыщего стека с текущего на следующую 
	delete p;//собсна удаляем стек
	return i;//возвращаем удаллёный элемент
}
struct queue {
	int inf;
	queue* next; //структура очень похожа на стек, даже содержащиеся поля идентичны
};
void push(queue*& h, queue*& t, int x) {// функция вставки элемента в начало очереди
	//уже можно заметить, что функция похожа на такую у стека, отличается она только тем, что нужно проверку, если очередь пустая
	queue* r = new queue;
	r->inf = x;
	r->next = nullptr;
	if (!h && !t) {//собсна сама проверка, нужно проверить, если оба указателя смотрят в пустоту, то по сути просто изначальную очередь представляем как ту, которую создали для решения
		h = t = r;
	}
	else {//иначе идём также как и со стеком, но в обратную сторону
		t->next = r;
		t = r;
	}
}
int pop(queue*& h, queue*& t) {//функция удаления первого элемента из очереди, почти полностью идентична таковой из стеков
	queue* r = h;
	int i = h->inf;
	h = h->next;
	if (!h) t = nullptr;//единственное отличие - это необходимость проверить, если мы вдруг удалили единственный элемент в очереди, то нужно обнулить и второй указатель 
	delete r;
	return i;
}
void BFS (vector<vector<int>> Gr, int n) {//функция обхода в ширину
	queue* h = nullptr;
	queue* t = nullptr;//создаём очередь 
	int x, y;
	bool Is_there_unvisited = true;
	int* a = new int[n];
	for (int i = 0; i < n; i++) a[i] = 0;//создаём массив а, регистрирующий посещение вершин
	cout << "Where would we start? ";
	cin >> x;//спрашиваем, откуда начинаем обход
	a[x] = 1;//регистрируем посещение начальной вершины
	push(h, t, x);//и добавляем сам узел в очередь
	cout << x;
	while (h && Is_there_unvisited) {
		x = pop(h, t);//достанем из очереди первый элемент
		for (int i = 0; i < Gr[x].size(); i++) {//также пройдём по остальным вершинам, смежным с тем, который мы достали из очереди 
			if (a[Gr[x][i]] == 0) {
				y = Gr[x][i];
				a[y] = 1;
				push(h, t, y);
				cout << y << " ";//тут операции, аналогичные тем, что мы выполняли для первого элемента
			}
		}
		Is_there_unvisited = false;
		for (int k = 0; k < n; k++) {
			if (a[k] == 0) {
				Is_there_unvisited = true;//при каждом завершении просмотра элементов, смежных с текущим будем проверять, если мы посетили все вершины, если да, то заканчиваем работу
				break;
			}
		}
	}
}
void DFS(vector<vector<int>> Gr, int n) {//функция обхода в глубину
	stack* h = nullptr;
	int x, y;
	bool fl = false;
	bool Is_there_unvisited = true;
	int* a = new int[n];
	for (int i = 0; i < n; i++) a[i] = 0;//создаём массив а, регистрирующий посещение вершин
	cout << "Where would we start? ";
	cin >> x;//спрашиваем, откуда начинаем обход
	a[x] = 1;//регистрируем посещение начальной вершины
	push(h, x);//и добавляем сам узел в стек
	cout << x<<" ";
	while (h && Is_there_unvisited) {
		x = h->inf;//рассмотрим из стека первый элемент
		for (int i = 0; i < Gr[x].size(); i++) {//также пройдём по остальным вершинам, смежным с тем, который мы достали из очереди 
			if (a[Gr[x][i]] == 0) {//если есть, смежная и непосещённая, то переходим к рассмотрению уже этой вершины
				y = Gr[x][i];
				fl = true;
				break;
			}
		}
		if (fl == true) {
			a[y] = 1;
			push(h, y);//если у рассмотренной вершины есть ещё смежные узлы, то также переходим к из рассмотрению
			cout << y;
		}
		else {
			pop(h);//иначе переходим к вершине, не смежной с предыдущей
		}
		Is_there_unvisited = false;
		for (int k = 0; k < n; k++) {
			if (a[k] == 0) {//проверяем, остались ли непосещённые вершины
				Is_there_unvisited = true;
				break;
			}
		}
		fl = false;//флаг, обозначающий наличие у узла смежных вершин бдуем постоянно обнулять, чтобы не уйти в вечный цикл из добавления в стек одних и тех же вершин
	}
}
int main() {
	int n, m, x, k, y, w;
	vector <vector<int>> Gr;//создаём двумерный вектор, выступающий в роли списка смежности
	cout << "Put a number of nodes " << endl;
	cin >> n;//спрашиваем число вершин
	for (int i = 0; i < n; i++) {
		Gr.push_back(vector<int>());
		cout << "Put number of neighbor nodes of current node " << i<<" ";
		cin >> k;
		cout << i<<" Neighbor nodes: ";
		for (int j = 0; j < k; j++) {
			cin >> w;
			Gr[i].push_back(w);//заполняем список смежности
		}
	}
	
	BFS(Gr, n);
	cout << endl;
	DFS(Gr, n);
}