dfs算法的python代码实现
时间: 2024-05-17 08:10:21 浏览: 13
DFS(深度优先搜索)是一种用于遍历或搜索树或图的算法。下面是 DFS 算法的 Python 代码实现:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
```
其中,`graph` 是一个字典类型,表示图的邻接表;`start` 是起始节点;`visited` 是已经访问过的节点集合。
该算法首先将起始节点加入到已访问集合中,并打印该节点。接着,对于该节点的每个未访问的相邻节点,递归调用 `dfs` 函数。最后,返回已访问节点的集合。
如果你有其他关于 DFS 算法的问题,欢迎提出。
相关问题
dfs算法python代码
以下是一个简单的深度优先搜索算法的Python代码实现:
```python
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` 是一个字典,表示图的邻接表,`start` 是搜索的起点。算法使用一个栈来保存待访问的节点,每次从栈中取出一个节点,如果该节点还没有被访问过,则将其加入已访问的集合,并将其邻接节点加入栈中。
请注意,这只是一个基本的深度优先搜索算法示例,实际应用中可能需要进行一些修改和优化。
dfs算法python实现
下面是DFS算法的Python实现示例:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set() # 创建一个空集合存储访问过的节点
visited.add(start) # 将起点加入到访问集合中
print(start) # 打印当前节点
for next_node in graph[start] - visited: # 遍历当前节点的邻接节点
dfs(graph, next_node, visited) # 对未访问的邻接节点进行深度优先搜索
return visited
```
其中,`graph`表示图的邻接表,`start`表示起点。在函数中,我们首先将起点加入到访问集合中,然后打印当前节点,接着遍历当前节点的邻接节点,对未访问的邻接节点进行深度优先搜索。最终,返回访问过的节点集合。