深度优先搜索 python
时间: 2023-10-12 12:06:19 浏览: 52
深度优先搜索(Depth First Search, DFS)是一种用于遍历或搜索树或图的算法。在Python中,可以使用递归或栈来实现深度优先搜索。
以下是一个使用递归实现深度优先搜索的示例代码:
```python
def dfs(graph, node, visited):
if node not in visited:
print(node)
visited.add(node)
neighbors = graph[node]
for neighbor in neighbors:
dfs(graph, neighbor, visited)
# 示例图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set()
dfs(graph, 'A', visited)
```
这段代码会按照深度优先的顺序遍历并打印图中的节点。其中,`graph` 是图的邻接表表示,`node` 是当前节点,`visited` 是已经访问过的节点集合。在每次递归调用时,我们检查当前节点是否已经被访问过,如果没有,则将其加入到已访问集合中,并递归地对其未访问的邻居节点进行深度优先搜索。
希望这个示例对你有帮助!如果你还有其他问题,请随时提问。
相关问题
深度优先搜索python
深度优先搜索(Depth First Search,DFS)是一种用于遍历或搜索树或图的算法。它从根节点开始,沿着每个分支尽可能深入,直到达到叶子节点或无法继续为止。然后回溯到上一个分支,继续探索其他分支。
以下是一个用Python实现深度优先搜索的示例代码:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 测试代码
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
dfs(graph, 'A')
```
输出结果为:A B D E F C
深度优先搜索Python实现
深度优先搜索(Depth-First Search,DFS)是一种常用的图遍历算法,它通过递归的方式从起始节点开始,沿着一条路径尽可能深入地搜索,直到无法继续为止,然后回溯到上一个节点,继续搜索其他路径。下面是深度优先搜索的Python实现:
```python
# 定义图的类
class Graph:
def __init__(self):
self.graph = {}
# 添加边
def add_edge(self, u, v):
if u in self.graph:
self.graph[u].append(v)
else:
self.graph[u] = [v]
# 深度优先搜索
def dfs(self, start):
visited = set() # 记录已访问的节点
self._dfs(start, visited)
def _dfs(self, node, visited):
visited.add(node)
print(node, end=" ") # 输出当前节点
neighbors = self.graph.get(node, [])
for neighbor in neighbors:
if neighbor not in visited:
self._dfs(neighbor, visited)
# 创建图对象
g = Graph()
# 添加边
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)
g.add_edge(3, 7)
# 从节点1开始进行深度优先搜索
print("深度优先搜索结果:")
g.dfs(1)
```
以上代码中,首先定义了一个`Graph`类来表示图,其中`add_edge`方法用于添加边,`dfs`方法用于进行深度优先搜索。在`_dfs`方法中,使用递归的方式进行深度优先搜索,并通过一个`visited`集合来记录已访问的节点,避免重复访问。