Wie kann die Tiefensuche gestoppt werden, wenn der Zielknoten des Graphen gefunden wird?

Question

Hier ist die grafische Darstellung:

g = { 
    0: [2, 5, 7], 
    1: [7], 
    2: [0, 6], 
    3: [5, 4], 
    4: [3, 6, 7], 
    5: [3, 4, 0], 
    6: [2, 4], 
    7: [0, 1, 4] 
} 

Ich habe die folgende Funktion in Python:

def dfs(graph, start, target, visited=None): 
    if visited is None: 
     visited = set() 
    visited.add(start) 

    for n in (set(graph[start]) - visited): 
     dfs(graph, n, target, visited) 
    return visited 

Aber es gibt alle Eckpunkte, die in der Grafik vorhanden ist, und ich möchte, dass Es gibt nur den Zielknoten zurück, wenn dieser im Diagramm vorhanden ist. Könnte mir jemand helfen?

Answer 1

Sie möchten testen, ob Sie Ihr Ziel erreicht haben, und wenn Sie dies getan haben, return True.

für Effizienz

def dfs(graph, start, target, visited=None): 
    if visited is None: 
     visited = set() 
    visited.add(start) 

    for n in (set(graph[start]) - visited): 
     if n == target: 
      return True 
     return dfs(graph, n, target, visited) 
    return False 

bearbeiten Kleine bearbeiten: Dies kann durch die folgenden Änderungen an Ihrem Code erreicht werden, ich habe einen Fehler in meinem Algorithmus, feste Version ist unter:

def dfs(graph, start, target, visited=None): 
    if start == target: 
     return True 
    if visited is None: 
     visited = set() 
    visited.add(start) 

    found = False 
    for n in (set(graph[start]) - visited): 
     if target == n: 
      return True 
     found = dfs(graph, n, target, visited) 
    return found