Tiefe erste Suche in einem ungerichteten, gewichteten Graph mit Adjazenzmatrix?

Question

Ich möchte nicht die Antwort, aber ich habe Probleme, die Knoten zu verfolgen. Was bedeutet, sage, ich habe Knoten 0, 1, 2, 3,4, 5, 6, 7, wobei 0 starten, und 7 ist das Ziel, machte ich eine Adjazenzmatrix wie so:

[ 
    [0, 3, 0, 0, 4, 0, 0, 0], 
    [3, 0, 0, 0, 5, 0, 8, 0], 
    [0, 0, 0, 4, 0, 5, 0, 0], 
    [0, 0, 4, 0, 0, 0, 0, 14], 
    [4, 5, 0, 0, 0, 2, 0, 0], 
    [0, 0, 5, 0, 2, 0, 4, 0], 
    [0, 8, 0, 5, 0, 4, 0, 0], 
    [0, 0, 0, 14, 0, 0, 0, 0] 
] 

wenn es eine ist 0, gibt es keine Verbindung zwischen den Knoten, andernfalls, wenn es größer als 1 ist, dann ist die Anzahl das Gewicht der Kante zwischen diesen Knoten.

Ich habe Probleme zu identifizieren, was der tatsächliche Knoten wäre, im Gegensatz zu einem Pfad.

Ich kann das Ziel finden, aber ich würde nicht wissen, wie man den Weg zum Ziel zeigt, und was das Gesamtgewicht wäre?

EDIT: Hier ist, was ich zu erreichen versuchen, (das wird nicht funktionieren, aber dies ist die allgemeine Idee):

def dfs(graph, start, goal): 
    stack = [] 
    visited = [] 

    stack.append(graph[start]) 
    visited.append(start) 

    while (len(stack) != 0): 
     current_node = stack.pop() 
     if current_node not in visited: 
      visited.append(current_node) 

     if current_node = goal: 
      return path 
     else: 
      for nodes in current_node: 
       if nodes not in visited: 
        stack.append(nodes) 

, wenn die Kanten nicht gewogene waren dies einfacher sein würde, aber ich bin im Grunde alle Nachbarn des aktuellen Knotens hinzufügen, solange ich es nicht auf dem Stapel besucht habe, bis ich den Zielknoten gefunden habe, und dann möchte ich den Pfad zurückgeben. aber in diesem Fall weiß ich, dass es kaputt ist, weil 1) ich nicht sicher bin, wie ich überprüfen kann, ob es der Zielknoten ist, da ich nur die Knoten-Nachbarn speichere und 2) nicht nach dem vollständigen Pfad suche.

Answer 1

Pflegen Sie eine path variable, um den Scheitelpunkt zu speichern, wenn Sie auf sie stoßen. Wenn Sie den Vertex end gefunden haben, hat die Pfadvariable den Pfad.

Suchen Sie den Pseudocode als Referenz. Verzeihen Sie einen kleinen Fehler im Code

DFS (vertex start, vertex end, Graph G, list path): 
     if(start==end): 
       return TRUE 
     for vertex in adjacent(start): 
      if vertex not in path:  # has not been traversed 
       path = path + [vertex] 
       a = DFS(vertex, end, G, path) 
       if a==TRUE: # end vertex was found 
        return TRUE 
       path.delete(vertex) # delete the vertex added,as its not in the path from start to end 

Acc. Wenn Sie den Zielknoten gefunden haben, enthält der besuchte Stapel das Element im Pfad zu Ihrem Code.

Ich hoffe, es hat geholfen.