python代码实现深度优先
时间: 2023-11-08 13:02:52 浏览: 43
以下是Python代码实现深度优先搜索算法的示例:
```python
def dfs(graph, start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
```
其中,`graph`是一个字典,用于存储图的邻接表;`start`是起始节点。
该算法的基本思想是从起始点开始,不断往他的下一层走,直到无法继续为止。然后回溯到上一个节点,再往他的下一层走,直到图中所有节点都被访问完为止。
相关问题
广度优先深度优先python 代码实现
好的,下面是Python实现广度优先搜索和深度优先搜索的示例代码:
广度优先搜索:
```python
from collections import deque
def bfs(graph, start, end):
queue = deque()
queue.append(start)
visited = set()
while queue:
node = queue.popleft()
if node == end:
return True
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
return False
```
深度优先搜索:
```python
def dfs(graph, start, end, visited=None):
if visited is None:
visited = set()
visited.add(start)
if start == end:
return True
for neighbor in graph[start]:
if neighbor not in visited:
if dfs(graph, neighbor, end, visited):
return True
return False
```
这里的`graph`是一个字典,表示图的邻接表,`start`是起点,`end`是终点。广度优先搜索使用了双端队列`deque`,深度优先搜索使用了递归。
用python实现深度优先算法
下面是使用Python实现深度优先搜索算法(DFS)的示例代码:
```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)
```
上面的代码实现了一个名为`dfs`的函数,它接受三个参数:`graph`表示图的邻接表表示法,`start`表示起始节点,`visited`用于记录已访问过的节点,默认为`None`。
算法首先将起始节点加入到已访问集合中,并输出节点值。然后递归地遍历起始节点的邻居节点,如果邻居节点没有被访问过,则调用`dfs`函数进行递归访问。
使用示例:
```python
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs(graph, 'A')
```
以上代码将会输出深度优先遍历结果:A B D E F C。
深度优先搜索算法通过递归方式遍历图的节点,一直沿着某个路径直到无法继续深入为止,然后回溯到前一个节点,继续遍历其他未访问的节点。这种算法适用于解决图的遍历问题和寻找路径问题。