实现图的深度优先遍历
时间: 2023-07-24 22:12:14 浏览: 47
图的深度优先遍历(Depth First Search, DFS)是一种用于遍历或搜索树或图的算法。它从一条随意的边开始遍历,然后尽可能远地遍历图的每个分支,直到到达不可遍历的节点为止。
以下是一个实现图的深度优先遍历的示例代码:
```python
# 定义图的节点类
class Node:
def __init__(self, val=None, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
# 深度优先遍历函数
def dfs(node, visited):
visited.add(node)
print(node.val)
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)
node1.neighbors = [node2, node4]
node2.neighbors = [node1, node3]
node3.neighbors = [node2, node4]
node4.neighbors = [node1, node3]
# 调用dfs函数遍历图
visited = set()
dfs(node1, visited)
```
输出结果为:
```
1
2
3
4
```