dfs算法python代码
时间: 2023-07-23 18:13:40 浏览: 40
以下是一个简单的深度优先搜索算法的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(深度优先搜索)是一种用于遍历或搜索树或图的算法。下面是 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
深度优先搜索(DFS)是一种常用的图遍历算法,用于遍历或搜索图或树的所有节点。在DFS中,从起始节点开始,沿着一条路径尽可能深入地探索,直到无法继续为止,然后回溯到上一个节点,继续探索其他路径。以下是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]
# DFS遍历
def dfs(self, start):
visited = set() # 用于记录已访问的节点
self._dfs(start, visited)
# 内部递归函数
def _dfs(self, node, visited):
visited.add(node)
print(node, end=" ")
if node in self.graph:
for neighbor in self.graph[node]:
if neighbor not in visited:
self._dfs(neighbor, visited)
```
使用示例:
```python
# 创建图对象
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)
# 从节点1开始进行DFS遍历
print("DFS遍历结果:")
g.dfs(1)
```
输出结果:
```
DFS遍历结果:
1 2 4 5 3 6
```