图的遍历算法 采用邻接表的DFS算法
时间: 2023-07-10 21:33:26 浏览: 58
图的遍历算法中,DFS(深度优先搜索)是一种常见的算法,可以用于查找图中的连通分量、寻找图中的路径等问题。以下是采用邻接表表示图的 DFS 算法的 Python 代码:
```python
# 定义节点类
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
# 定义 DFS 函数
def dfs(node, visited):
# 访问当前节点
print(node.val)
# 标记当前节点为已访问
visited.add(node)
# 递归遍历节点的邻居节点
for neighbor in node.neighbors:
if neighbor not in visited:
dfs(neighbor, visited)
# 创建图
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node1.neighbors = [node2, node3]
node2.neighbors = [node1, node4, node5]
node3.neighbors = [node1, node6]
node4.neighbors = [node2, node5]
node5.neighbors = [node2, node4]
node6.neighbors = [node3]
# 遍历图
visited = set()
dfs(node1, visited)
```
在这段代码中,我们定义了一个 Node 类来表示图中的节点,每个节点包含一个值(val)和一个邻居节点列表(neighbors)。我们使用邻接表来表示整个图。然后,我们定义了一个 dfs 函数来进行深度优先遍历。我们从起始节点开始遍历,并对每个节点进行访问。在访问每个节点之前,我们将其标记为已访问,以避免重复访问。接着,我们递归遍历该节点的邻居节点,并对每个邻居节点进行同样的操作。最后,我们创建了一个 visited 集合来保存已经访问过的节点,以确保每个节点只被访问一次。