BFS(广度优先搜索)和DFS(深度优先搜索)是两种常用的图遍历算法。目标检查是在图中查找目标节点的过程。
下面是使用BFS和DFS解决目标检查问题的示例代码:
BFS示例代码:
from collections import deque
def bfs(graph, start, target):
queue = deque([start])
visited = set()
while queue:
node = queue.popleft()
visited.add(node)
if node == target:
return True
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
return False
# 示例图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
start_node = 'A'
target_node = 'F'
if bfs(graph, start_node, target_node):
print("目标节点存在")
else:
print("目标节点不存在")
DFS示例代码:
def dfs(graph, start, target, visited=set()):
visited.add(start)
if start == target:
return True
for neighbor in graph[start]:
if neighbor not in visited:
if dfs(graph, neighbor, target, visited):
return True
return False
# 示例图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
start_node = 'A'
target_node = 'F'
if dfs(graph, start_node, target_node):
print("目标节点存在")
else:
print("目标节点不存在")
以上示例代码中,我们使用邻接表表示图,通过调用bfs
和dfs
函数进行目标检查。其中,bfs
函数使用队列实现广度优先搜索,dfs
函数使用递归实现深度优先搜索。
下一篇:BFS和DFS实现-建议和改进