深度优先搜索的基本实现:
python
# 定义图结构
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# 深度优先搜索函数
def dfs(graph, node, visited):
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbour in graph[node]:
dfs(graph, neighbour, visited)
# 使用dfs函数
visited = set() # 使用集合存储访问过的节点
dfs(graph, 'A', visited)
这段代码中,我们首先定义了一个简单的图结构graph。然后定义了一个深度优先搜索的函数dfs。这个函数接受一个图、一个节点和一个已访问节点的集合作为参数。如果节点没有被访问过,我们就将其打印出来,并将其加入到已访问节点的集合中。然后,对于这个节点的每一个邻居节点,我们递归地调用dfs函数。
在这个例子中,我们的图有6个节点('A','B','C','D','E'和'F'),其中'A'是源节点。在调用dfs函数时,我们从'A'开始遍历这个图。
联系客服