图的遍历代码实现

图是一种数据结构，它由顶点和边组成。图的遍历是指按照一定的规则，访问图中的所有节点，而不重复。图的遍历分为深度优先遍历和广度优先遍历，它们都有不同的实现方法。

深度优先遍历（DFS）

深度优先遍历是一种递归算法，它沿着图的深度遍历图的节点。从一个节点开始，如果它有未被访问的相邻节点，就选择一个未被访问的节点进行递归访问。如果所有相邻节点都被访问过，就回溯到上一个节点继续遍历。

深度优先遍历的实现方法有两种：递归和栈。

递归实现深度优先遍历的代码如下：

```python

visited = set() # 已访问节点集合

def dfs(graph, vertex):

visited.add(vertex)

for neighbor in graph[vertex]:

if neighbor not in visited:

dfs(graph, neighbor)

```

栈实现深度优先遍历的代码如下：

```python

visited = set()

def dfs(graph, start):

stack = [start] # 堆栈初始化，将初始节点入栈

while stack:

vertex = stack.pop() # 出栈

if vertex not in visited:

visited.add(vertex)

stack.extend(graph[vertex] - visited) # 将未访问过的相邻节点入栈

```

广度优先遍历（BFS）

广度优先遍历是从起始节点开始，按照广度优先的顺序访问节点。首先访问起始节点，接着访问和起始节点相邻的所有节点，然后访问这些节点的相邻节点，直到所有节点都被访问。

广度优先遍历的实现方法是使用队列。

广度优先遍历的代码实现如下：

```python

visited = set()

def bfs(graph, start):

queue = [start] # 队列初始化，将初始节点入队

while queue:

vertex = queue.pop(0) # 出队

if vertex not in visited:

visited.add(vertex)

queue.extend(graph[vertex] - visited) # 将未访问过的相邻节点入队

```