import java.util.*;

public class GraphTraversals{
    //define the graph using an adjacency matrix.
    private int[][] graph = { {0,1,0,0,0,0,0,1,0}, {1,0,1,0,0,0,0,1,0}, {0,1,0,1,0,0,0,1,0},
                              {0,0,1,0,0,0,1,0,1}, {0,0,0,0,0,1,1,0,0}, {0,0,0,0,1,0,0,0,0},
                              {0,0,0,1,1,0,0,1,0}, {1,1,1,0,0,0,1,0,0}, {0,0,0,1,0,0,0,0,0}};
    
    private boolean visited[];
    
    public GraphTraversals(){
        visited = new boolean[graph.length];
        Arrays.fill(visited, false);
        System.out.println("The depth first traversal result of the graph is -");
        DepthFirstTraversal(0); //recursion, starting from node #0
        Arrays.fill(visited, false);
        System.out.println("The depth first traversal result of the graph is -");
        DepthFirstTraversal2(0); //recursion, starting from node #0
        Arrays.fill(visited, false);
        System.out.println("\nThe breadth first traversal result of the graph is -");
        BreadthFirstTraversal(0);
    }    
    
    public void DepthFirstTraversal(int firstNode){  //prints out the nodes in order visited
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(firstNode);
        visited[firstNode] = true;
        while(!stack.empty()){
            int currentNode = stack.pop().intValue();
             System.out.print(currentNode + " ");
            for(int i=0; i<graph[currentNode].length; i++)
                if(graph[currentNode][i]!=0 && !visited[i]){
                    stack.push(i);
                    visited[i] = true;  //actually just discovered, will be visited when pop
                }
        }
        System.out.println();
    }
    
    public void DepthFirstTraversal2(int currentNode){  //prints out the nodes in order visited
        System.out.print(currentNode + " ");
        visited[currentNode] = true;
        for(int i=0; i<graph[currentNode].length; i++)
            if(graph[currentNode][i]!=0 && !visited[i])
                DepthFirstTraversal2(i);
    }
    
    public void BreadthFirstTraversal(int firstNode){  //prints out the nodes in order visited
        Queue<Integer> queue = new LinkedList<Integer>();
        System.out.print(firstNode + " ");
        visited[firstNode] = true;
        queue.offer(firstNode);
        while(!queue.isEmpty()){
            int currentNode = queue.poll().intValue();
            for(int i=0; i<graph[currentNode].length; i++)
                if(graph[currentNode][i]!=0 && !visited[i]){
                    System.out.print(i + " ");
                    visited[i] = true;
                    queue.offer(i);
                }
        }
        System.out.println();
    }
    
    public static void main(String args[]){ 
        new GraphTraversals(); 
    }
}