图的层次遍历

**图的层次遍历**

图是一种非常重要的数据结构，它可以用来表示复杂的关系网络。层次遍历是图的一种常见操作，涉及从图中访问每个节点的顺序。这种操作在很多应用场景中都很有用，比如图像处理、社交网络分析等。

**什么是图的层次遍历**

图的层次遍历是一种从图中访问每个节点的顺序，按照一定的规则进行访问。这种操作通常涉及以下几个步骤：

1.选择一个起始节点作为当前节点。
2. 访问当前节点所连接的所有邻居节点。
3. 将当前节点标记为已访问，以免重复访问。
4. 重复步骤2和3，直到所有节点都被访问。

**图的层次遍历算法**

有很多种实现图的层次遍历的算法，其中最常见的是广度优先搜索（BFS）和深度优先搜索（DFS）。下面我们将分别介绍这两种算法。

### 广度优先搜索（BFS）

广度优先搜索是一种从起始节点开始，按照层次顺序访问所有邻居节点，然后再访问更远的邻居节点的算法。这种算法通常使用队列来实现。

**代码示例**

from collections import dequedef bfs(graph, start):
 """
 Performs a breadth-first search on the graph starting from the given node.

 Args:
 graph (dict): The graph represented as an adjacency list.
 start (node): The node to start the search from.

 Returns:
 A list of nodes in the order they were visited.
 """
 visited = set()
 queue = deque([start])
 result = []

 while queue:
 node = queue.popleft()
 if node not in visited:
 visited.add(node)
 result.append(node)

 # Add all unvisited neighbors to the queue for neighbor in graph[node]:
 if neighbor not in visited:
 queue.append(neighbor)

 return result# Example usage:
graph = {
 'A': ['B', 'C'],
 'B': ['D', 'E'],
 'C': ['F'],
 'D': [],
 'E': ['F'],
 'F': []
}

print(bfs(graph, 'A')) # Output: ['A', 'B', 'C', 'D', 'E', 'F']

def dfs(graph, start):
 """
 Performs a depth-first search on the graph starting from the given node.

 Args:
 graph (dict): The graph represented as an adjacency list.
 start (node): The node to start the search from.

 Returns:
 A list of nodes in the order they were visited.
 """
 visited = set()
 stack = [start]
 result = []

 while stack:
 node = stack.pop()
 if node not in visited:
 visited.add(node)
 result.append(node)

 # Add all unvisited neighbors to the stack for neighbor in graph[node]:
 if neighbor not in visited:
 stack.append(neighbor)

 return result# Example usage:
graph = {
 'A': ['B', 'C'],
 'B': ['D', 'E'],
 'C': ['F'],
 'D': [],
 'E': ['F'],
 'F': []
}

print(dfs(graph, 'A')) # Output: ['A', 'C', 'F', 'E', 'D', 'B']