/********************************************************
*                          								 *
* Przeszukiwanie grafu w głąb i wszerz      		     *
* Program zostal pobrany ze strony www.algorytm.org 	 *
*                           							 *
* Autor:    Dawid Drozd		            				 *
* www.algorytm.org             							 *
*********************************************************/

/*
 * Program zawiera funkcje które pokazują jak działają spokojnie
 *  można je usunać.
 * Polecam przeanalizować BFS a DFS różnią się może 3-4 linijkami
 * głównie zamiana stosu na kolejkę
 * */

#include <cstdio>
#include <stack>
#include <queue>
using namespace std;

const int n = 7;//Rozmiar macierzy incydencji

//Funkcja pomocnicza do wizualizacji dzialania//////////////////////////

queue<int>VODWIEDZONE;//POmocniczy stos do symulacji odwiedzonych

void pokaz_odwiedzone()
{
	//Jakie już odwiedziliśmy
	queue<int>kopia = VODWIEDZONE;
	printf("Juz odwiedzone: ");
	while(!kopia.empty())
	{
		printf("%d  ",kopia.front());
		kopia.pop();
	}
}

void pokaz_zawartosc_stosu_i_odwiedzone(stack<int> stos)
{
	pokaz_odwiedzone();
	if(stos.empty())
	{
		printf("\nStos PUSTY!\n");
		return;
	}
	
	printf("\nZawartosc stosu:\n%d<--------- TOP\n",stos.top());
	stos.pop();
	while(!stos.empty())
	{
		printf("%d\n",stos.top());
		stos.pop();
	}
}

void pokaz_zawartosc_kolejki_i_odwiedzone(queue<int> kolejka)
{
	pokaz_odwiedzone();
	if(kolejka.empty())
	{
		printf("\nKolejka PUSTA!\n");
		return;
	}
	
	printf("\nZawartosc kolejki: %d",kolejka.front());
	kolejka.pop();
	while(!kolejka.empty())
	{
		printf("  %d",kolejka.front());
		kolejka.pop();
	}
}
////////////////////////////////////////////////////////////////////////

//////////////////DFS///////////////////////////////////////////////////
void DFS(int G[n][n],int szukany)
{
	stack<int> stos;
	bool V[n];
	for(int j=0;j<n;++j)V[j] = false;//Wierzchołki nie odwiedzone
	
	stos.push(szukany);//Wrzucamy startujący wierzchołek na stos
	
	while(!stos.empty())
	{
		pokaz_zawartosc_stosu_i_odwiedzone(stos);//Do symulacji
		
		
		szukany = stos.top();
		stos.pop();//Usuwamy odwiedzany element
		
		printf("\nOdwiedzam: %d\n",szukany);
		
		VODWIEDZONE.push(szukany);//Do symulacji odwiedzonych
		
		V[szukany] = true;//ODwiedziliśmy już ten
		
		for(int j = n-1;j >= 0;--j)
		{
			if(G[j][szukany] != 0 && V[j] == false)
			{
				stos.push(j);//Wrzucamy na stos jego sąsiadów
				V[j] = true;//Znaznaczamy ,że go odwiedzimy!(w niedalekiej przyszłości)
				//Inaczej będziemy mieli np taką sytuację w stosie 2,3,4,2 <-- 2x dwójka
			}
		}
	}
	
	pokaz_zawartosc_stosu_i_odwiedzone(stos);//Do symulacji
}
////////////////////////////////////////////////////////////////////////



//////////////////BFS///////////////////////////////////////////////////

void BFS(int G[n][n],int szukany)
{
	queue<int> kolejka;
	
	bool V[n];
	for(int j=0;j<n;++j)V[j] = false;//Wierzchołki nie odwiedzone
	
	kolejka.push(szukany);//Wrzucamy startujący wierzchołek na kolejke
	
	while(!kolejka.empty())
	{
		pokaz_zawartosc_kolejki_i_odwiedzone(kolejka);//Do symulacji
		
		
		szukany = kolejka.front();
		kolejka.pop();//Usuwamy odwiedzany element
		
		printf("\n\nOdwiedzam: %d\n",szukany);
		
		VODWIEDZONE.push(szukany);//Do symulacji odwiedzonych
		
		V[szukany] = true;//ODwiedziliśmy już ten
		
		for(int j = 0;j < n;++j)
		{
			if(G[j][szukany] != 0 && V[j] == false)
			{
				kolejka.push(j);//Wrzucamy na stos jego sąsiadów
				V[j] = true;//Znaznaczamy ,że go odwiedzimy!(w niedalekiej przyszłości)
				//Inaczej będziemy mieli np taką sytuację w stosie 2,3,4,2 <-- 2x dwójka
			}
		}
	}
	
	pokaz_zawartosc_kolejki_i_odwiedzone(kolejka);//Do symulacji
	
}
////////////////////////////////////////////////////////////////////////

int main()
{
	//Przykład ze strony: http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html
	int tab[n][n] = {
					{0, 0, 0, 0, 0, 0, 0},
					{0, 0, 0, 0, 1, 0, 0},
					{0, 1, 0, 0, 0, 0, 0},
					{0, 1, 0, 0, 0, 0, 0},
					{0, 0, 1, 1, 0, 1, 0},
					{0, 0, 1, 0, 0, 0, 0},
					{0, 0, 0, 1, 0, 0, 0}
					};
					
					
	printf("DFS\n\n");			
	DFS(tab,1);//Odpalamy DFS'a z wierzchołka 1
	
	while(!VODWIEDZONE.empty())VODWIEDZONE.pop();//Czyszczenie
	
	printf("\n\nBFS\n\n");	
	BFS(tab,1);//Odpalamy BFS'a z wierzchołka 1
	
	return 0;
}