视频字幕
图的遍历是计算机科学中的重要概念，指按照某种规则访问图中的每一个顶点一次且仅一次。其目的是系统地访问图中的所有顶点和边。在C++中，主要有两种遍历方法：广度优先搜索BFS和深度优先搜索DFS。
广度优先搜索BFS的原理是从起始顶点开始，逐层访问其所有邻居，然后再访问这些邻居的邻居。实现时通常使用队列来存储待访问的顶点。BFS的特点是适用于查找无权图的最短路径、查找连通分量以及进行层次遍历。
深度优先搜索DFS的原理是从起始顶点开始，沿着一条路径尽可能深地访问，直到不能继续为止，然后回溯到前一个顶点，继续探索其他未访问的分支。实现时通常使用栈或递归。DFS适用于查找连通分量、拓扑排序、检测环以及生成树等应用。
在C++中实现图遍历时，需要注意几个要点。首先是图的数据结构，通常使用邻接矩阵或邻接表来表示图。其次是访问标记，需要使用布尔数组或集合来标记已访问的顶点，这样可以避免重复访问和陷入死循环。这里展示了使用邻接表和BFS的基本实现代码。
总结一下，图遍历是系统访问图中所有顶点的重要算法。BFS使用队列实现，适合求最短路径和层次遍历。DFS使用栈或递归实现，适合连通性检测和拓扑排序。在C++实现时，需要选择合适的数据结构表示图，并使用访问标记避免重复访问。这两种算法在不同应用场景下各有优势。