Algorithmensammlung: Graphentheorie: Tiefensuche

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Algorithmensammlung: Graphentheorie

Tiefensuche[Bearbeiten]

Die Tiefensuche ist ein Suchverfahren zum Auffinden von Knoten in Graphen. Es geht dabei zunächst in die Tiefe, durchsucht also die verschiedenen adjazenten Knoten um den Startknoten zu mitunter sehr unterschiedlichen Zeitpunkten.

Für nähere Informationen siehe auch  Tiefensuche.


Java[Bearbeiten]

int tiefensuche(boolean[][] matrix,int[] nodelist ,boolean[] nodelistvisited  ,int current,int suche){
    // Beim ersten Aufruf der Methode wird current als Startwert verwendet.
    // current gibt außerdem an, an welchem Index in der Adjazensmatrix man sich gerade befindet.
    // matrix ist eine Adjazensmatrix.
    // nodelist ist ein Feld, in dem sich alle Knoten des Graphen befinden; zu beachten ist, dass sich der Index des Feldes mit dem der Matrix deckt.
    if (nodelist[current]==suche) return current;
    else {
        nodelistvisited[current]=true; // Knoten als besucht kennzeichnen
        for (int i=0;i<nodelist.length-start-1;i++)
        {
            if(matrix[current][i] && !nodelistvisited[i]) tiefensuche (matrix,nodelist,nodelistvisited,i,suche);
        }
    return -1; // leider nicht gefunden
    }}

Python[Bearbeiten]

def tiefensuche(adj, start, suche, besucht=[]):
    # adj ist die Adjazenzliste {knoten: [kanten]}
    # start ist der Knoten, um die Suche zu beginnen
    # suche ist der gesuchte Knoten
    if start == suche:
        return True
    if adj[start]:
        for knoten in filter(lambda x: x not in besucht, adj[start]):
            besucht.append(knoten)
            if tiefensuche(adj, knoten, suche, besucht):
                return True
    return False