import java.util.*;

class Kante{
	  Knoten ziel;
	  int laenge;
	  Kante (Knoten k, int l){ziel=k; laenge=l;}
	} 

class Knoten{
    String  name;
    boolean markiert;
    int dist;
    ArrayList<Kante> nachbarn;
    Knoten(String s){ name = s; nachbarn = new ArrayList<Kante>();}
    public String toString(){ return name;}
}

class Graph{
	  
	  int knotenZahl;
    Knoten[] knotenArray; 
    
    Graph(){
    	Knoten bonn     = new Knoten("Bonn"),       frankfurt = new Knoten("Frankfurt"), 
	           fulda    = new Knoten("Fulda"),      gießen    = new Knoten("Gießen"), 
	           kassel   = new Knoten("Kassel"),     köln      = new Knoten("Köln"),
	           mannheim = new Knoten("Mannheim"),   marburg   = new Knoten("Marburg"), 
	           würzburg = new Knoten("Würzburg");
           
      Knoten[] ka = {bonn,frankfurt,fulda,gießen,kassel,köln,mannheim,marburg,würzburg};
		  knotenArray = ka;
		  knotenZahl  = ka.length;
	    
	     //Kanten definieren
	    bonn.nachbarn.add(new Kante(frankfurt,181));
	    bonn.nachbarn.add(new Kante(köln,34));
	    bonn.nachbarn.add(new Kante(mannheim,224));
	    
	    frankfurt.nachbarn.add(new Kante(bonn,181));
	    frankfurt.nachbarn.add(new Kante(fulda,104));
	    frankfurt.nachbarn.add(new Kante(gießen,66));
	    frankfurt.nachbarn.add(new Kante(mannheim,88));
	    frankfurt.nachbarn.add(new Kante(würzburg,136));
	    
	    fulda.nachbarn.add(new Kante(frankfurt,104));
	    fulda.nachbarn.add(new Kante(gießen,106));
	    fulda.nachbarn.add(new Kante(kassel,96));
	    fulda.nachbarn.add(new Kante(würzburg,93));
	    
	    gießen.nachbarn.add(new Kante(frankfurt,66));
	    gießen.nachbarn.add(new Kante(fulda,106));
	    gießen.nachbarn.add(new Kante(köln,174));
	    gießen.nachbarn.add(new Kante(marburg,30));
	    
	    kassel.nachbarn.add(new Kante(fulda,96));
	    kassel.nachbarn.add(new Kante(marburg,104));
	    
	    köln.nachbarn.add(new Kante(bonn,34));
	    köln.nachbarn.add(new Kante(gießen,174));
	    
	    mannheim.nachbarn.add(new Kante(bonn,224));
	    mannheim.nachbarn.add(new Kante(frankfurt,88));
	    
	    marburg.nachbarn.add(new Kante(gießen,30));
	    marburg.nachbarn.add(new Kante(kassel,104));
	    
	    würzburg.nachbarn.add(new Kante(frankfurt,136));
	    würzburg.nachbarn.add(new Kante(fulda,93));
	    
	  }

 void resetMarken(){for (Knoten k : knotenArray) k.markiert = false;}
 void resetDist(){for (Knoten k : knotenArray) k.dist = 0;}
    
    
    int index(Knoten k){
    	  for (int i=0; i < knotenZahl; i++)
            if (k == knotenArray[i]) return i;
        return -1;    
        }    
    
    int index(String s){
    	  for (int i=0; i < knotenZahl; i++)
            if (s.equals(knotenArray[i].name)) return i;
        return -1;    
        }
        
    Knoten find(String s){
    	  for (int i=0; i < knotenZahl; i++)
            if (s.equals(knotenArray[i].name)) return knotenArray[i];
        return null;    
        }    
    
    int kante(int k1, Knoten k2){
    	  for (Kante k : knotenArray[k1].nachbarn)
            if (k.ziel == k2) return k.laenge;
        return -1;    
        }
        
    /*boolean kante(Knoten k1, Knoten k2){
    	  for (int i=0; i < knotenZahl; i++)
            if (k1 == knotenArray[i]) return kante(i,k2);
        return false;    
        }*/ 
        
    int kante(Knoten k1, Knoten k2){
    	  for (Knoten i1 : knotenArray)
    	    if (i1 == k1) for (Kante k : k1.nachbarn)
    	       if (k.ziel == k2) return k.laenge;
        return -1;    
        }           

    void nachbarn(){
    	for (Knoten k1 : knotenArray)
    	  for (Kante k : k1.nachbarn)
    		  System.out.println("Kante von "+k1+" nach "+k.ziel+" vorhanden. Länge ist: "+k.laenge);
    		}       
    

    void tiefenSuche(Knoten k){
        resetMarken();
        rekTiefenSuche(k);
        }
        
    void rekTiefenSuche(Knoten k){
        k.markiert = true;
        System.out.println(k);
        for (Kante kan : k.nachbarn)
        	  if (!kan.ziel.markiert) rekTiefenSuche(kan.ziel);    
       }
       
    void breitenSuche(Knoten k){
        resetMarken();
	      LinkedList<Knoten> queue = new LinkedList<Knoten>();
	      k.markiert = true;
	      queue.add(k);
	      while(!queue.isEmpty()){
		         Knoten kq = queue.removeFirst();
		         System.out.println(kq);
		         for (Kante kan : kq.nachbarn)
        	       if (!kan.ziel.markiert) {
        	       	 kan.ziel.markiert= true;
        	       	 queue.add(kan.ziel);
        	         }
             }   
	      }

     void minSuche(Knoten u, Knoten v){
     	 System.out.println("Von " + u);
     	 resetDist();
     	 HashSet<Knoten> s1 = new HashSet<Knoten>(); 
     	 HashSet<Knoten> s2 = new HashSet<Knoten>();
     	 s1.add(u);
     	 for (Kante k : u.nachbarn) s2.add(k.ziel);
     	 while (!s1.contains(v)){
	     	 // Suche Kante aus s2, die nach s1 befördert werden kann 
	     	 Knoten knotenMin = null;
	     	 int distMin = Integer.MAX_VALUE;
	     	 for (Knoten k1 : s1)
	     	   for (Knoten k2 : s2){
	     	   	 int dk = kante(k1,k2);
	     	   	 if (dk>0){ 
	     	   	   int distNeu = k1.dist + dk;
	     	   	   if (distNeu < distMin){
	     	   	   	 distMin = distNeu;
	     	   	   	 knotenMin = k2;
	     	   	   	}
	     	   	  }
	     	   	}
	     	  // Update von s1 und s2
	     	  knotenMin.dist = distMin;
	     	  System.out.println("nach "+ knotenMin + " ist die Distanz: " + distMin );
	     	  s1.add(knotenMin);
	     	  s2.remove(knotenMin); 
	     	  for (Kante k : knotenMin.nachbarn) if (!s1.contains(k.ziel)) s2.add(k.ziel);
     	  }
    }

}

public class GraphT {

    static String start = "Bonn";
    static String ziel = "Kassel";
    
    public static void main(String args[]) {
        System.out.println("Graph Tester");
        Graph  g = new Graph();
        Knoten k1 = g.find(start);
        if (k1 == null) {System.out.println("Knoten " + start + " nicht im Graph gefunden!");return;}
        Knoten k2 = g.find(ziel);
        if (k2 == null) {System.out.println("Knoten " + ziel + " nicht im Graph gefunden!");return;}
        
        /**/
        System.out.println("Tiefensuche");
	      g.tiefenSuche(k1);
	      System.out.println("Breitensuche");
	      g.breitenSuche(k1);
	      
	      
	      System.out.println("Dijkstras Min Suche");
	      g.minSuche(k1, k2);
	      System.out.println("Von " + start + " nach " + ziel + " ist die Distanz: " + k2.dist);
   }
}