Блог

Я пытаюсь создать список всех возможных путей из заданной точки на графике в другую. график выложен на сетке размером 5×6, пробелы b1 и c1 отсутствуют. при выполнении функции для поиска всех путей я сталкиваюсь с ошибкой индекса, когда функция выполняется в любом из 6 пространств строк. Я не уверен, как это исправить, поскольку я не понимаю, как индекс может быть вне диапазона, поскольку он является самореферентным.

 class Graph: 

def __init__(self, vertices): 
    # No. of vertices 
    self.V = vertices  
      
    # default dictionary to store graph 
    self.graph = defaultdict(list)  

# function to add an edge to graph 
def addEdge(self, u, v): 
    self.graph[u].append(v) 
    
    

'''A recursive function to print all paths from 'u' to 'd'. 
visited[] keeps track of vertices in current path. 
path[] stores actual vertices and path_index is current 
index in path[]'''
def printAllPathsUtil(self, u, d, visited, path): 

    # Mark the current node as visited and store in path 
    visited[u]= True
    path.append(u) 

    # If current vertex is same as destination, then print 
    # current path[] 
    if u == d: 
        print (path) 
    else: 
        # If current vertex is not destination 
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[u]: 
            if visited[i]== False: 
                self.printAllPathsUtil(i, d, visited, path) 
                  
    # Remove current vertex from path[] and mark it as unvisited 
    path.pop() 
    visited[u]= False


# Prints all paths from 's' to 'd' 
def printAllPaths(self, s, d): 

    # Mark all the vertices as not visited 
    visited =[False]*(self.V) 

    # Create an array to store paths 
    path = [] 

    # Call the recursive helper function to print all paths 
    self.printAllPathsUtil(s, d, visited, path) 
 

вот график:

 g = Graph()
g.addEdge(3,1)
g.addEdge(6,2)

g.addEdge(3,4)
g.addEdge(5,4)
g.addEdge(5,6)
g.addEdge(4,3)
g.addEdge(4,5)
g.addEdge(6,5)

g.addEdge(7,3)
g.addEdge(8,4)
g.addEdge(9,5)
g.addEdge(10,6)

g.addEdge(7,8)
g.addEdge(8,9)
g.addEdge(9,10)
g.addEdge(8,7)
g.addEdge(9,8)
g.addEdge(10,9)

g.addEdge(11,7)
g.addEdge(12,8)
g.addEdge(13,9)
g.addEdge(14,10)

g.addEdge(11,12)
g.addEdge(12,13)
g.addEdge(13,14)
g.addEdge(12,11)
g.addEdge(13,12)
g.addEdge(14,13)

g.addEdge(15,11)
g.addEdge(16,12)
g.addEdge(17,13)
g.addEdge(18,14)

g.addEdge(15,16)
g.addEdge(16,17)
g.addEdge(17,18)
g.addEdge(16,15)
g.addEdge(17,16)
g.addEdge(18,17)

g.addEdge(19,15)
g.addEdge(20,16)
g.addEdge(21,17)
g.addEdge(22,18)

g.addEdge(19,20)
g.addEdge(20,21)
g.addEdge(21,22)
g.addEdge(20,19)
g.addEdge(21,20)
g.addEdge(22,21)

g.addEdge(1,0)
g.addEdge(4,0)
g.addEdge(5,0)
g.addEdge(2,0)
#name nodes
a1=1; d1=2; a2=3; b2=4;c2=5;d2=6;a3=7;b3=8;c3=9;d3=10;a4=11;b4=12;c4=13;d4=14;a5=15;b5=16;c5=17;d5=18;a6=19;b6=20;c6=21;d6=22;door=0
 

И, наконец, ошибка:

 ---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-67-885dbfadd65a> in <module>
----> 1 g.printAllPaths(a6, door)

<ipython-input-61-eecc5a16716f> in printAllPaths(self, s, d)
     50 
     51         # Call the recursive helper function to print all paths
---> 52         self.printAllPathsUtil(s, d, visited, path)

<ipython-input-61-eecc5a16716f> in printAllPathsUtil(self, u, d, visited, path)
     33             for i in self.graph[u]:
     34                 if visited[i]== False:
---> 35                     self.printAllPathsUtil(i, d, visited, path)
     36 
     37         # Remove current vertex from path[] and mark it as unvisited

<ipython-input-61-eecc5a16716f> in printAllPathsUtil(self, u, d, visited, path)
     33             for i in self.graph[u]:
     34                 if visited[i]== False:
---> 35                     self.printAllPathsUtil(i, d, visited, path)
     36 
     37         # Remove current vertex from path[] and mark it as unvisited

<ipython-input-61-eecc5a16716f> in printAllPathsUtil(self, u, d, visited, path)
     32             # Recur for all the vertices adjacent to this vertex
     33             for i in self.graph[u]:
---> 34                 if visited[i]== False:
     35                     self.printAllPathsUtil(i, d, visited, path)
     36 

IndexError: list index out of range
 

связано ли это с тем, что в 6-й строке меньше индексов? вывод, предшествующий ошибке, кажется, успешно перечисляет все пути, но ошибка прерывает выполнение функции после шестой строки первого столбца.

Спасибо!

Не знаю, почему это сработало, но добавление дополнительных двух вершин с индексами направления от 0 решило эту проблему. Мне все равно хотелось бы получить совет относительно того, почему это устранило ошибку, поскольку я полностью в неведении.