import java.util.*;

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

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

class Graph{
	  
	  int knotenZahl;
    Knoten[] knotenArray; 
    
    Graph(){
    	Knoten sFra = new Knoten(0, "San Francisco"), sRaf = new Knoten(1, "San Rafael"), 
	           rich = new Knoten(2, "Richmond"),      oakl = new Knoten(3, "Oakland"), 
	           sMat = new Knoten(4, "San Mateo"),     hayw = new Knoten(5, "Hayward"),
	           palo = new Knoten(6, "Palo Alto"),     frem = new Knoten(7, "Fremont"), 
	           sJos = new Knoten(8, "San Jose"),      sCla = new Knoten(9, "Santa Clara"),
	           scot = new Knoten(10, "Scotts Valley"), wats = new Knoten(11, "Watsonville"),
	           sCru = new Knoten(12, "Santa Cruz"),    half = new Knoten(13, "Half Moon Bay"),
	           paci = new Knoten(14, "Pacifica");
           
      Knoten[] ka = {sFra,sRaf,rich,oakl,sMat,hayw,palo,frem,sJos,sCla,scot,wats,sCru,half,paci};
		  knotenArray = ka;
		  knotenZahl  = ka.length;
	    
	     //Kanten definieren
	    sFra.nachbarn.add(new Kante(sRaf,18));
	    sFra.nachbarn.add(new Kante(oakl,12));
	    sFra.nachbarn.add(new Kante(sMat,20));
	    sFra.nachbarn.add(new Kante(paci,15));
	    
	    sRaf.nachbarn.add(new Kante(rich,15));
	    sRaf.nachbarn.add(new Kante(sFra,18));
	    
	    rich.nachbarn.add(new Kante(oakl,15));
	    rich.nachbarn.add(new Kante(sRaf,15));
	    
	    oakl.nachbarn.add(new Kante(hayw,20));
	    oakl.nachbarn.add(new Kante(sFra,12));
	    oakl.nachbarn.add(new Kante(rich,15));
	    
	    sMat.nachbarn.add(new Kante(hayw,20));
	    sMat.nachbarn.add(new Kante(palo,18));
	    sMat.nachbarn.add(new Kante(half,25));
	    sMat.nachbarn.add(new Kante(sFra,20));
	    
	    hayw.nachbarn.add(new Kante(frem,14));
	    hayw.nachbarn.add(new Kante(sMat,20));
	    hayw.nachbarn.add(new Kante(oakl,20));
	    
	    palo.nachbarn.add(new Kante(frem,15));
	    palo.nachbarn.add(new Kante(sCla,10));
	    palo.nachbarn.add(new Kante(sMat,18));
	    
	    frem.nachbarn.add(new Kante(sJos,20));  
	    frem.nachbarn.add(new Kante(palo,15));
	    frem.nachbarn.add(new Kante(hayw,14));
	    
	    sJos.nachbarn.add(new Kante(wats,60));
	    sJos.nachbarn.add(new Kante(sCla,15));
	    sJos.nachbarn.add(new Kante(frem,20));
	    
	    sCla.nachbarn.add(new Kante(sJos,15));
	    sCla.nachbarn.add(new Kante(scot,35));
	    sCla.nachbarn.add(new Kante(palo,10));
	    
	    scot.nachbarn.add(new Kante(sCla,35));
	    scot.nachbarn.add(new Kante(sCru,10));
	    
	    wats.nachbarn.add(new Kante(sCru,70));
	    wats.nachbarn.add(new Kante(sJos,60));
	    
	    sCru.nachbarn.add(new Kante(scot,10));
	    sCru.nachbarn.add(new Kante(wats,70));
	    sCru.nachbarn.add(new Kante(half,50));
 
	    half.nachbarn.add(new Kante(sMat,25));
	    half.nachbarn.add(new Kante(sCru,50));
	    half.nachbarn.add(new Kante(paci,15));
	    
	    paci.nachbarn.add(new Kante(sFra,15));
	    paci.nachbarn.add(new Kante(half,15));
	    
	  }

 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.print(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.print(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 eine Kante k2 aus s2,  
	     	 // die das nächste Element von S1 werden soll
	     	 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 startTS = "Palo Alto";
    static String startBS = "Palo Alto";
    static String start = "San Rafael";
    static String ziel = "Scotts Valley";
    
    public static void main(String args[]) {
        System.out.println("Graph Tester");
        Graph  g = new Graph();
        Knoten kTS = g.find(startTS);
        if (kTS == null) {System.out.println("Knoten " + start + " nicht im Graph gefunden!");return;}
        Knoten kBS = g.find(startBS);
        if (kBS == null) {System.out.println("Knoten " + start + " nicht im Graph gefunden!");return;}
        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(kTS);
	      System.out.println();
	      System.out.println("Breitensuche");
	      g.breitenSuche(kBS);
	      System.out.println();
	      
	      System.out.println("Dijkstras Min Suche");
	      g.minSuche(k1, k2);
	      System.out.println("Von " + start + " nach " + ziel + " ist die Distanz: " + k2.dist);
   }
}