图是一种非常重要的数据结构，在计算机科学中有着广泛的应用。图的遍历是图的基本操作之一，是指从图的某一顶点出发，按照一定的规则依次访问图中的所有顶点。本文将详细介绍图的遍历方法，包括广度优先遍历和深度优先遍历两种方法。
一、广度优先遍历
广度优先遍历是从图的某一顶点出发，按照距离逐层访问图中的所有顶点。具体步骤如下
1. 从起始顶点开始，将该顶点标记为已访问。
2. 将该顶点的所有邻接顶点加入到一个队列中。
3. 从队列的头部取出一个顶点，将其标记为已访问。
4. 将该顶点的所有未访问的邻接顶点加入到队列的尾部。
5. 重复步骤3~4，直到队列为空。
二、深度优先遍历
深度优先遍历是从图的某一顶点出发，按照深度优先的原则访问图中的所有顶点。具体步骤如下
1. 从起始顶点开始，将该顶点标记为已访问。
2. 从该顶点的邻接顶点中选择一个未访问的顶点，将其作为下一个起始顶点，重复步骤1。
3. 如果该顶点的所有邻接顶点都已经被访问过，则回溯到上一个顶点，重复步骤2。
4. 重复步骤1~3，直到所有顶点都被访问过。
图的遍历是图的基本操作之一，在实际应用中非常重要。广度优先遍历和深度优先遍历是两种常用的图遍历方法，它们的不同之处在于遍历顺序的不同。在实际应用中，可以根据具体情况选择合适的遍历方法。
