/**
 * 
 * @author MartLipi
 *
 */

//trida vrchol
class top{
	int index;
	char color;
	top(int index){
		this.index=index;
	}
}

//trida graph
class graph{
	String graphName;
	int[][] matrix;
	int arrayLenght;
	top[] topArray;
	int[] visited;
	int last=0;

	//konstruktor tridy graph - build - in graph
	graph(){
		int topCount=3;
		this.graphName="testGraph";
		this.matrix=new int[topCount+1][topCount+1];			
		this.arrayLenght=topCount+1;
		this.topArray=new top[topCount+1];
		this.visited=new int[topCount+1];
		for( int i = 1; i < topCount+1; i++ ){ 			
			topArray[i] = new top(i); 
			topArray[i].color = 'W';
		}
		//naplneni matice
		this.matrix[1][1]=0;
		this.matrix[1][2]=1;
		this.matrix[1][3]=1;

		this.matrix[2][1]=0;
		this.matrix[2][2]=0;
		this.matrix[2][3]=0;

		this.matrix[3][1]=1;
		this.matrix[3][2]=0;
		this.matrix[3][3]=0;
	}
	
	
	//konstruktor tridy graph - mozno zadat delku a jmeno
	graph(String graphName, int topCount){
		this.graphName=graphName;
		this.matrix=new int[topCount+1][topCount+1];
		this.arrayLenght=topCount+1;
		this.topArray=new top[topCount+1];
		this.visited=new int[topCount+1];
		for( int i = 1; i < topCount+1; i++ ){ 			
			topArray[i] = new top(i); 
			topArray[i].color = 'W';
		}
	}

	//naplni matici souslednosti
	void putNeighbours(){
		System.out.println("Definujte hrany uspo?adanych dvojic(0=neexistuje, 1=existuje)");
		for ( int r = 1; r < arrayLenght; r++ ){
			for ( int s = 1; s < arrayLenght; s++ ){
				if (r!=s){
					System.out.print(r + " -> " + s +": " );
					matrix[r][s]=VstupData.ctiInt();
				}else{matrix[r][s]=0;}
			}
		}
	}

	void matrixPrintf(){	
		for ( int r = 1; r < arrayLenght; r++ ){
			for ( int s = 1; s < arrayLenght; s++ ){
				System.out.print(matrix[r][s]+" ");
			}
			System.out.println();
		}
	}
	
	//vraci index dalsiho souseda
	int nextNeigbour( int r,int s ){
		s++;												
		if ( s < arrayLenght ){			
			while(matrix[r][s]==0 ){ 						
				s++;
				if (s==arrayLenght){return(-1);}
			}
			return(s);														
		}else{return(-1);}									
	}
	
	//prohledavani do sirky BFS
	void searchBFS (int s){
		visited[1]=s;
		last=1;
		System.out.print(s+" ");
		
		intFrontaSpoj f = new intFrontaSpoj();	
		topArray[s].color = 'G';										
		f.push(s);											
		
		while(!f.empty()) {							
			int selected = f.pop();						
			int neighbour = nextNeigbour(selected,0);									 
			while(neighbour !=(-1)){						
				if (topArray[neighbour].color == 'W') {		
					topArray[neighbour].color  = 'G';			
					visited[++last] = neighbour;
					System.out.print(neighbour+" ");		
					f.push(neighbour);							
				}				
				neighbour = nextNeigbour(selected,neighbour);			
			}	
			topArray[selected].color = 'B';									
		}		
		System.out.println();
		System.out.println();		
	}		

	//prohledavani do hloubky DFS
	void searchDFS (int s) {
		topArray[s].color = 'G';							
		visited[++last] = s;
		System.out.print(s+" ");							
		int neighbour = nextNeigbour(s,0);					
		
		while ( neighbour!=(-1) ) {							
			if (topArray[neighbour].color == 'W') {			
				searchDFS(neighbour);							
			}
			neighbour = nextNeigbour(s,neighbour);               
		}
		topArray[s].color = 'B';                         
		}
	}			

public class grafMatice {
	public static void main( String[] args ) {	
//		System.out.println("Zadej Pocet Vrcholu");
		graph testGraph1 = new graph();  
		graph testGraph2 = new graph();  

		
//		testGraph.putNeighbours();
		testGraph1.matrixPrintf();
		
		System.out.println("Ze ktereho vrcholu hledat?");
		int v=VstupData.ctiInt();
		testGraph1.searchBFS(v);
		testGraph2.searchDFS(v);
	}
	
}