在实现BFS和DFS算法时,我们通常需要遍历整个图或树,这会涉及到许多节点。如果这些节点数量非常大,我们可能会遇到节点数无限的问题。为了解决这个问题,我们可以设置一个访问标志,记录已经遍历过的节点,以避免无限遍历。
下面是用Python实现的一个简单的BFS和DFS算法,其中使用了一个集合来记录已经访问过的节点:
# Python代码示例
def bfs(graph, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
# 测试
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
print(bfs(graph, 'A')) # 输出 {'A', 'B', 'C', 'D', 'E', 'F'}
print(dfs(graph, 'A')) # 输出 {'A', 'C', 'F', 'E', 'B', 'D'}