如何在 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] * numvisited[start_point] = 1stack = []stack.append(start_point)l = [] #used to store the final pathl.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 stackreturn 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 list

graph = {

    '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 Code

dfs(visited, graph, 'A')

这就是 dfs 的工作原理