python - 如何在深度优先遍历中分离路线？

Question

我有两条公交路线。我想找到源和目的地之间的可能路径。我使用深度优先遍历来查找所有可能的路径。这里是路径。这里橙色的路径是1号巴士经过的路径。红色的路径是乘坐 2 号巴士。所以从1到4的乘客应该从1到3，下车然后乘坐2路公交车。

这是我尝试过的。

# Python program to print all paths from a source to destination. 

from collections import defaultdict 

#This class represents a directed graph 
# using adjacency list representation 
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) 



# Create a graph given in the above diagram 
g = Graph(5) 
g.addEdge(1, 2) 
g.addEdge(2, 3) 
g.addEdge(3, 4)









s = 1 ; d = 4
print ("Following are all different paths from %d to %d :" %(s, d)) 
g.printAllPaths(s, d)

预期输出：

[1,2,3]
[3,4]

目前的输出：

[1,2,3,4]

标签： python