Algorithmensammlung: Graphentheorie: Tiefensuche

Algorithmensammlung: Graphentheorie

• Algorithmus von Kruskal
• Algorithmus von Prim
• Breitensuche (BFS - breadth first search)
• Dijkstra-Algorithmus
• Tiefensuche (DFS - depth first search)

Tiefensuche

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

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; // aktuell betrachteter Knoten ist der gesuchte Knoten
	}
    else {
        
		nodelistvisited[current] = true; // Knoten als besucht markieren
		
        for (int i=0;i<nodelist.length-1;i++) // Alle Knoten durchgehen
        {
			int value;
			
            if(matrix[current][i] && !nodelistvisited[i]) { // Wenn Knoten erreichbar und noch nicht besucht
				value = tiefensuche(matrix, nodelist, nodelistvisited, i, suche); //Rekursionsaufruf
				
				if(value != -1) {
					return value; // Knoten gefunden
				}
			}
        }
		
		return -1; // leider nicht gefunden
    }
}

Python

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