如何在 dfs 算法（python）中实现目标状态？

Question

我正在尝试使用 DFS 来遍历我的图。我的功能是dfs(cost_matrix, start_point, goals_array). 我将 DFS 算法到达任何一个目标状态所遵循的路径放在一个列表中。我似乎无法弄清楚在遍历期间何时从列表中追加和弹出项目。我知道一旦达到目标状态我就可以退出循环。我正在迭代地使用DFS的堆栈方法。

def DFS_Traversal(cost, start_point, goals):

num = len(cost)

visited = [0] * num

visited[start_point] = 1

stack = []

stack.append(start_point)

l = [] #used to store the final path

l.append(start_point)

while(len(stack)):

    s = stack.pop()

    if(visited[s] == 0):

        visited[s] = 1

        if s in goals:

            break

        for i in range (1, num): #going across the matrix

            if (cost[s][i] != -1 || cost[s][i] != 0):

                stack.append(i) #adding members to the stack

return l

Answer 1

进行了一些修改，以适应问题中的要求，并在找到目标之一时中断 - 从这里：from collections import defaultdict   # This class represents a directed graph using # adjacency list representation class Graph:       # Constructor     def __init__(self):           # 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 function used by DFS     def DFSUtil(self, v, visited, goals):           # Mark the current node as visited          # and print it         print(" ")        visited[v] = True        for goal in goals:            if v == goal:                print(f"found {v} - finish!")                return        print(v, end = ' ')           # Recur for all the vertices          # adjacent to this vertex         for i in self.graph[v]:             if visited[i] == False:                 self.DFSUtil(i, visited, goals)       # The function to do DFS traversal. It uses     # recursive DFSUtil()     def DFS(self, v, goals):           # Mark all the vertices as not visited         visited = [False] * (max(self.graph)+1)           # Call the recursive helper function          # to print DFS traversal         self.DFSUtil(v, visited, goals)   # Driver code   # Create a graph given  # in the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3)   print("Following is DFS from (starting from vertex 2)") g.DFS(2, [1,4]) 输出：Following is DFS from (starting from vertex 2) 2  0  found 1 - finish!

Answer 2

# Using a Python dictionary to act as an adjacency listgraph = {    'A' : ['B','C'],    'B' : ['D', 'E'],    'C' : ['F'],    'D' : [],    'E' : ['F'],    'F' : []}visited = set() # Set to keep track of visited nodes.def dfs(visited, graph, node):    if node not in visited:        print (node)        visited.add(node)        for neighbour in graph[node]:            dfs(visited, graph, neighbour)# Driver Codedfs(visited, graph, 'A')这就是 dfs 的工作原理