Suchen in Graphen

In vielen Anwendungen muss man alle Knoten eines Graphen durchsuchen. Z.B. bei der Suche nach einem Schatz oder dem Ausgang in einem Labyrinth wird man einen Weg weiterverfolgen, bis man in einer Sackgasse landet oder an einer Kreuzung ankommt, von der aus man bereits alle Wege erkundet hat. Dieses Vorgehen nennt man Tiefensuche. Dem gegenüber steht die Breitensuche, die u.a. bei der Bestimmung eines Kürzesten-Wege-Baumes in ungewichteten Graphen verwendet wird. Beide Algorithmen erzeugen aufspannende Bäume in Graphen, deren Gestalt jedoch sehr unterschiedlich ist.
In dem folgenden Applet können Tiefen- und Breitensuche auf einem beliebigen Graphen gestartet und beobachtet werden. Die unterschiedliche Gestalt der jeweiligen Ergebnisse wird besonders gut erkennbar, indem die Algorithmen automatisch ausgeführt werden und dann zwischen Breiten- und Tiefensuche umgeschaltet wird.
 Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen.

Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. Knoten bewegen Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. neuer Knoten Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. neue Kante Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. Objekt löschen

Der Suchalgorithmus ist in der folgenden Funktion implementiert. Der boolsche Parameter dfs steuert dabei, ob Tiefensuche oder Breitensuche verwendet werden soll.
 
// Graphensuch-Algorithmus: Tiefensuche oder Breitensuche
// start gibt den Startknoten an.
// Der boolsche Parameter dfs gibt an, ob Tiefensuche verwendet werden soll
// animation gibt an, ob der Algorithmus animiert werden soll
graphsearch(start,dfs,animation):={
   //Lokale Variablen
   createvar(warteliste);
   createvar(aktiv);
   createvar(dist);
   createvar(kanten);
   createvar(nachbar);
 
   // Jeder knoten erhält am Anfang eine Entfernungsmarkierung von -1
   forall(allvertices(), setMark(#,"Distanz",-1));
 
   // Färbe alle Knoten und Kanten schwarz
   setGraphColor([0,0,0],[0,0,0],1.0,0.2);
 
   if(animation,blink([start],3));
 
   // Markiere den Startknoten mit Distanz 0
   start.color=[0,0,0];
   start.size=10;
   setMark(start,"Distanz",0);
 
   // Erzeuge eine Warteliste, in der markierte aber noch nicht fertige Knoten gespeichert werden sollen.
   // packe Startknoten in Warteliste
   warteliste=[start];
 
   // starte Suche
   while(length(warteliste)>0,
 
       // nimm ersten Knoten der Warteliste
       aktiv=warteliste_1;
       if(animation,blink([aktiv],10));
 
       // Schaue nach Entfernung des aktiven
       dist=getMark(aktiv,"Distanz");
    
       // nimm die erste ausgehenden Kanten zu unbesuchtem Nachbarn
       kanten=select(incidentedges(aktiv),
                     getMark(neighbor(aktiv,#),"Distanz")<0);
       // gibt es so eine?
       if (length(kanten)>0,
           // besuche den Nachbarn
           nachbar=neighbor(aktiv,kanten_1);
 
           if(animation,blink([aktiv,kanten_1,nachbar],10));
 
           // Nachbar noch unmarkiert?
           if( getMark(nachbar,"Distanz")<0,
              //Markiere den Nachbarn
              nachbar.color=getLevelColor(dist);
              (kanten_1).color=nachbar.color;
              (kanten_1).alpha=1.0;
              setMark(nachbar,"Distanz",dist+1);
 
              // Tiefensuche oder Breitensuche?
              if (dfs,
                  warteliste=[nachbar]++warteliste,
                  warteliste=warteliste++[nachbar]; 
              );        
           );
       ,
         // ansonsten: alle Nachbarn besucht, Knoten ist fertig, lösche ihn
         warteliste=remove(warteliste,aktiv);
       );
   );
 
   //Lokale Variablen
   removevar(warteliste);
   removevar(aktiv);
   removevar(dist);
   removevar(kanten);
   removevar(nachbar);
};

Das Interessante an dieser Implementation ist, dass sich Tiefensuche und Breitensuche nur in der Zeile
 
             if (dfs,
                 warteliste=[nachbar]++warteliste,
                 warteliste=warteliste++[nachbar]; 
              );

unterscheiden, also ob der nächste zu untersuchende Knoten an den Anfang oder das Ende der Warteliste gepackt wird. Bei Tiefensuche wird folglich ein Stack (Stapel), bei Breitensuche eine Queue (Warteschlange) verwendet.

weiter >