Блог

Я пытаюсь использовать 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
  

Взято и немного изменено, чтобы соответствовать требованию в вопросе и прерываться при нахождении одной из целей — отсюда:

 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!
  

 # 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