// chapitre 5 queue parcours graphe.cpp : définit le point d'entrée pour l'application console.
//

#include "stdafx.h"

#include <iostream>
#include <queue>

using namespace std;

#define N 4

bool**init_graphe()
{
	bool**graphe;
	graphe=new bool*[N];

	graphe[0]=new bool[N];
	
	graphe[0][0]=false;		// true lorsqu'il y a une adjacence
	graphe[0][1]=true;
	graphe[0][2]=true;
	graphe[0][3]=true;
	
	graphe[1]=new bool[N];
	graphe[1][0]=false;
	graphe[1][1]=false;
	graphe[1][2]=true;
	graphe[1][3]=true;
	
	graphe[2]=new bool[N];
	graphe[2][0]=false;
	graphe[2][1]=true;
	graphe[2][2]=false;
	graphe[2][2]=true;

	graphe[3]=new bool[N];
	graphe[3][0]=false;
	graphe[3][1]=false;
	graphe[3][2]=false;
	graphe[3][3]=false;	
	
	return graphe;
}

queue<int> file;
bool*sommets_visites;

void visite(bool**graphe,int n,int sommet)
{
	if(sommets_visites[sommet])
		return;

	sommets_visites[sommet]=true;
	cout << "Visite du sommet " << (sommet+1) << endl;

	// cherche toutes les adjacences non visitées
	for(int i=0; i<n; i++)
		if(graphe[sommet][i] && ! sommets_visites[i])
			file.push(i);
}

void parcours_largeur(bool**graphe,int n)
{
	sommets_visites=new bool[n];
	for(int i=0; i<n; i++)
		sommets_visites[i]=false;	// sommet pas visité

	file.push(0);			// part du sommet 1
	
	while(! file.empty())
	{
		int s=file.front();
		file.pop();
		visite(graphe,n,s);
	}
}

int main(int argc, char* argv[])
{
	bool**graphe;
	graphe=init_graphe();

	parcours_largeur(graphe,N);
	return 0;
}

