写一个深度优先搜索算法的代码
时间: 2024-05-08 17:15:10 浏览: 16
以下是一个深度优先搜索算法的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`函数。最后返回已经访问过的节点集合。
相关问题
用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 = {'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}}
dfs(graph, 'A')
```
该代码定义了一个名为 dfs 的函数,接受一个 graph(表示图的邻接表)、一个 start(表示起始节点) 和一个 visited(表示已访问的节点集合)作为参数。默认的 visited 值为 None,即第一次调用 dfs 函数时,visited 将被初始化为空集合。
函数内部首先将起始节点 start 加入 visited 集合中,并输出其值。接着遍历与该节点相邻且未被访问过的节点,对这些节点递归调用 dfs 函数,直到所有节点都被访问完毕。
最后返回 visited 集合,表示所有被访问过的节点。
写一个深度优先算法的代码
答:def dfs(node):
# 访问当前节点
visit(node)
# 访问当前节点所有相邻节点
for n in node.neighbors:
if not n.visited:
dfs(n)
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)