クラスインスタンスを追加するために追加する

Question

私は2つのノード間の最短経路を見つけるためにコードを実装していますが、 なぜDFS関数の最初の行を変更すると出力も変わります。

path += [start]はpath = path + [start]に相当しますか？変更前

出力が変更した後に::

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 

です::

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 

コード::

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)) 

です。注意::このコードは、この本からですenter link description here

Answer 1

彼らは

path += [start]がpath.extend([start])と同等である同じではありません - それは変異しpath。一方

path = path + [start]は、新しいリストと名前それstartを作成します。

は、以下の実験を考えてみましょう、とIDの点に注意してください。

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

bのIDが変更されたがaのIDはしませんでした。

なぜあなたのコードに違いがあるのか​​ - DFSは機能です。 path += [start]を使用するバージョンでは、渡されたパラメータpathを変更しています。この変更は、呼び出しが返された後も維持されます。一方、path = path + [start]を使用するバージョンでは、pathという名前の新しいローカル変数を作成します。pathに変更を加えることなく、呼び出しが戻ったときに範囲外になる変数を作成します。ライン

path=path+[start] 

で

Answer 2

新しいリストオブジェクトを作成します。ライン

path+=[start] 

あなたはすでに存在しているリストオブジェクトを変更するには

。

あなたはこれを試すことができます。

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