深度优先搜索的Python语言模板
时间: 2023-11-05 09:02:56 浏览: 37
# 定义深度优先搜索函数
def dfs(node, visited):
# 如果当前节点已经被访问过,则返回
if visited[node]:
return
# 标记当前节点为已访问
visited[node] = True
# 处理当前节点
# ...
# 递归遍历当前节点的邻居节点
for neighbor in node.neighbors:
dfs(neighbor, visited)
# 创建图的节点类
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
# 创建图的节点
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
# 构建图的邻接表
node1.neighbors = [node2, node3]
node2.neighbors = [node1]
node3.neighbors = [node1]
# 初始化节点访问状态
visited = [False] * 3
# 从节点1开始进行深度优先搜索
dfs(node1, visited)
相关问题
深度优先搜索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`集合来记录已访问的节点,避免重复访问。
python深度优先搜索模板
以下是 Python 的深度优先搜索模板:
```
visited = set()
def dfs(node):
# 如果节点已经被访问过,直接返回
if node in visited:
return
# 访问当前节点
visited.add(node)
# 处理当前节点
# ...
# 递归访问当前节点的邻居节点
for neighbor in node.neighbors:
dfs(neighbor)
```
这是一个基本的深度优先搜索模板,其中 visited 是一个集合,用于记录已经访问过的节点。在 dfs 函数中,首先判断当前节点是否已经被访问过,如果是,则直接返回;否则,将当前节点加入 visited 集合中,并处理当前节点。然后,递归访问当前节点的邻居节点。