public class AdjGraph {

   private boolean [][] edges;  // adjacent matrix
   private Object [] labels;

   public AdjGraph (int n) {
      edges = new boolean [n][n];
      labels = new Object[n];
   }


   public int size() { return labels.length; }

   public void   setLabel (int vertex, Object label) { labels[vertex]=label; }
   public Object getLabel (int vertex)               { return labels[vertex]; }

   public void    addEdge    (int source, int target)  { edges[source][target] = true; }
   public boolean isEdge     (int source, int target)  { return edges[source][target]; }
   public void    removeEdge (int source, int target)  { edges[source][target] = false; }

   public int [] neighbors (int vertex) {
      int count = 0;
      for (int i=0; i<edges[vertex].length; i++) {
	 if (edges[vertex][i]) count++;
      }
      final int[]answer= new int[count];
      count = 0;
      for (int i=0; i<edges[vertex].length; i++) {
	 if (edges[vertex][i]) answer[count++]=i;
      }
      return answer;
   }

   public void print () {
      for (int j=0; j<edges.length; j++) {
	 System.out.print (labels[j]+": ");
	 for (int i=0; i<edges[j].length; i++) {
	    if (edges[j][i]) System.out.print (labels[i]+" ");
	 }
	 System.out.println ();
      }
   }

   public void depthFirstPrintRecurse (int start) {
      boolean [] marked = new boolean [size()]; // all false;
      depthFirstRecurse (start, marked);
   }

   public void depthFirstRecurse (int v, boolean[] marked) {
      marked[v]=true;
      System.out.println (getLabel(v));

      final int [] connections = neighbors(v);
      for (int i=0; i<connections.length; i++) {
	 final int n = connections[i];
	 if (!marked[n]) depthFirstRecurse (n, marked);
      }
   }

   public void breadthFirstPrint (final int start) {
      final boolean [] marked = new boolean [size()]; // all false;
      final IntQueue q = new IntQueue ();
      
      System.out.print ("BF traversal: ");
      q.addRear (start);
      while (!q.isEmpty()) {
         final int v = q.removeFront ();
	 marked[v]=true;
	 System.out.print (getLabel(v)+" ");
	 
	 final int [] connections = neighbors(v);
	 for (int i=0; i<connections.length; i++) {
	    final int n = connections[i];
	    if (!marked[n]) q.addRear (n);
         }
      }
      System.out.println ();
   }

   public void depthFirstPrint (final int start) {
      final boolean [] marked = new boolean [size()]; // all false;
      final IntStack st = new IntStack ();
      
      System.out.print ("DF traversal: ");
      st.addFront (start);
      while (!st.isEmpty()) {
         final int v = st.removeFront ();
	 marked[v]=true;
	 System.out.print (getLabel(v)+" ");
	 
	 final int [] connections = neighbors(v);
	 for (int i=connections.length-1; i>=0; i--) {
	 final int n = connections[i];
	    if (!marked[n]) st.addFront (n);
         }
      }
      System.out.println ();
   }

   public static void main (String args[]) {
      final AdjGraph t = new AdjGraph (7);
      t.setLabel (0, "v0");
      t.setLabel (1, "v1");
      t.setLabel (2, "v2");
      t.setLabel (3, "v3");
      t.setLabel (4, "v4");
      t.setLabel (5, "v5");
      t.setLabel (6, "v6");
      t.addEdge (0,1);
      t.addEdge (0,4);
      t.addEdge (1,3);
      t.addEdge (2,0);
      t.addEdge (3,0);
      t.addEdge (3,6);
      t.addEdge (3,5);
      t.addEdge (6,1);
      t.print();

      t.depthFirstPrint (0);
      t.breadthFirstPrint (0);
      t.depthFirstPrintRecurse (0);
   }
}