Hinzufügen zu einer Klasseninstanz

Question

Ich implementiere einen Code, um den kürzesten Weg zwischen zwei Knoten zu finden, aber warum, wenn ich die erste Zeile der DFS-Funktion ändern die Ausgabe auch. Ist es nicht wahr, dass

path += [start] entspricht path = path + [start]?

die Ausgabe vor dem Wechsel ist ::

Current DFS path: 0 
Current DFS path: 0->1 
Current DFS path: 0->1->2 
Current DFS path: 0->1->2->3 
Current DFS path: 0->1->2->3->4 
Current DFS path: 0->1->2->3->5 
Current DFS path: 0->1->2->4 
Current DFS path: 0->2 
Current DFS path: 0->2->3 
Current DFS path: 0->2->3->1 
Current DFS path: 0->2->3->4 
Current DFS path: 0->2->3->5 
Current DFS path: 0->2->4 
shortest path is 0->2->3->5 

nach Veränderung ::

Current DFS path: 0 
Current DFS path: 0->1 
Current DFS path: 0->1->2 
Current DFS path: 0->1->2->3 
Current DFS path: 0->1->2->3->4 
Current DFS path: 0->1->2->3->4->5 
shortest path is 0->1->2->3->4->5 

Der Code ::

class Node(object): 
    def __init__(self, name): 
     """Assumes name is a string""" 
     self.name = name 
    def getName(self): 
     return self.name 
    def __str__(self): 
     return self.name 

class Edge(object): 
    def __init__(self, src, dest): 
     """Assumes src and dest are nodes""" 
     self.src = src 
     self.dest = dest 
    def getSource(self): 
     return self.src 
    def getDestination(self): 
     return self.dest 
    def __str__(self): 
     return self.src.getName() + '->' + self.dest.getName() 

class WeightedEdge(Edge): 
    def __init__(self, src, dest, weight = 1.0): 
     """Assumes src and dest are nodes, weight a number""" 
     self.src = src 
     self.dest = dest 
     self.weight = weight 
    def getWeight(self): 
     return self.weight 
    def __str__(self): 
     return self.src.getName() + '->(' + str(self.weight) + ')'\ 
       + self.dest.getName() 

#Figure 12.8 
class Digraph(object): 
    #nodes is a list of the nodes in the graph 
    #edges is a dict mapping each node to a list of its children 
    def __init__(self): 
     self.nodes = [] 
     self.edges = {} 
    def addNode(self, node): 
     if node in self.nodes: 
      raise ValueError('Duplicate node') 
     else: 
      self.nodes.append(node) 
      self.edges[node] = [] 
    def addEdge(self, edge): 
     src = edge.getSource() 
     dest = edge.getDestination() 
     if not (src in self.nodes and dest in self.nodes): 
      raise ValueError('Node not in graph') 
     self.edges[src].append(dest) 
    def childrenOf(self, node): 
     return self.edges[node] 
    def hasNode(self, node): 
     return node in self.nodes 
    def __str__(self): 
     result = '' 
     for src in self.nodes: 
      for dest in self.edges[src]: 
       result = result + src.getName() + '->'\ 
         + dest.getName() + '\n' 
     return result[:-1] #omit final newline 

class Graph(Digraph): 
    def addEdge(self, edge): 
     Digraph.addEdge(self, edge) 
     rev = Edge(edge.getDestination(), edge.getSource()) 
     Digraph.addEdge(self, rev) 

#Figure 12.9 
def printPath(path): 
    """Assumes path is a list of nodes""" 
    result = '' 
    for i in range(len(path)): 
     result = result + str(path[i]) 
     if i != len(path) - 1: 
      result = result + '->' 
    return result 

def DFS(graph, start, end, path, shortest, toPrint = False): 
    """Assumes graph is a Digraph; start and end are nodes; 
      path and shortest are lists of nodes 
     Returns a shortest path from start to end in graph""" 
    path = path + [start] 
    if toPrint: 
     print('Current DFS path:', printPath(path)) 
    if start == end: 
     return path 
    for node in graph.childrenOf(start): 
     if node not in path: #avoid cycles 
      if shortest == None or len(path) < len(shortest): 
       newPath = DFS(graph, node, end, path, shortest, 
           toPrint) 
       if newPath != None: 
        shortest = newPath 
    return shortest 

def shortestPath(graph, start, end, toPrint = False): 
    """Assumes graph is a Digraph; start and end are nodes 
     Returns a shortest path from start to end in graph""" 
    return DFS(graph, start, end, [], None, toPrint) 

#Figure 12.10 
def testSP(): 
    nodes = [] 
    for name in range(6): #Create 6 nodes 
     nodes.append(Node(str(name))) 
    g = Digraph() 
    for n in nodes: 
     g.addNode(n) 
    g.addEdge(Edge(nodes[0],nodes[1])) 
    g.addEdge(Edge(nodes[1],nodes[2])) 
    g.addEdge(Edge(nodes[2],nodes[3])) 
    g.addEdge(Edge(nodes[2],nodes[4])) 
    g.addEdge(Edge(nodes[3],nodes[4])) 
    g.addEdge(Edge(nodes[3],nodes[5])) 
    g.addEdge(Edge(nodes[0],nodes[2])) 
    g.addEdge(Edge(nodes[1],nodes[0])) 
    g.addEdge(Edge(nodes[3],nodes[1])) 
    g.addEdge(Edge(nodes[4],nodes[0])) 
    sp = shortestPath(g, nodes[0], nodes[5]) 
    print('Shortest path found by DFS:', printPath(sp)) 

Hinweis :: dieser Code aus diesem Buch enter link description here

Answer 1

Sie sind nicht die gleichen

path += [start]-path.extend([start]) entspricht - es mutiertpath.

Auf der anderen Seite

path = path + [start] erstellt eine neue Liste und Namen es start.

Betrachten Sie das folgende Experiment, und notieren Sie die IDs:

>>> a = [1] 
>>> id(a) 
55937672 
>>> a += [2,3] 
>>> id(a) 
55937672 
>>> b = [1] 
>>> id(b) 
55930440 
>>> b = b + [1,2] 
>>> id(b) 
55937288 

Die ID b geändert, aber die ID a nicht.

Warum es einen Unterschied in Ihrem Code macht - DFS ist eine Funktion. In der Version, die path += [start] verwendet, ändern Sie den übergebenen Parameter path - und diese Änderung bleibt bestehen, nachdem der Aufruf zurückgegeben wird. Auf der anderen Seite, in der Version, die path = path + [start] verwendet, erstellen Sie eine neue lokale Variable mit dem Namen path, eine, die außerhalb des Geltungsbereichs, wenn der Aufruf zurückkehrt, ohne Änderungen an dem Parameter path.

Answer 2

In Zeile

path=path+[start] 

Sie neue Liste erstellen Objekt.

In Zeile

path+=[start] 

Sie List-Objekt ändern, die bereits vorhanden ist.

Sie können dies versuchen:

path2=path[:] 
path2+=[start]