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

2023-08-22 16:41:42

## 2 回答

HUH函数

TA贡献1836条经验 获得超4个赞

from collections import defaultdict

# This class represents a directed graph using

class Graph:

# Constructor

def __init__(self):

# default dictionary to store graph

self.graph = defaultdict(list)

# function to add an edge to graph

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

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()

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!

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)

for neighbour in graph[node]:

dfs(visited, graph, neighbour)

# Driver Code

dfs(visited, graph, 'A')

• 2 回答
• 0 关注
• 1248 浏览

0/150