我正在嘗試使用 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
2 回答
HUH函數
TA貢獻1836條經驗 獲得超4個贊
進行了一些修改，以適應問題中的要求，并在找到目標之一時中斷 - 從這里：
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!
慕的地8271018
TA貢獻1796條經驗 獲得超4個贊
# 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 的工作原理
添加回答
舉報
0/150
提交
取消