图的遍历方式

在计算机科学中，图(Graph)是由一组节点和一组边组成的数据结构。图用于表示不同对象之间的关系，如网络拓扑、社交网络、地图等。图的遍历是指按照一定的规则访问图的所有节点，以便获取图中的信息。图的遍历方式分为深度优先遍历（DFS）和广度优先遍历（BFS）两种。

深度优先遍历（DFS）

深度优先遍历是一种先序遍历的方法，即从图的某个起始节点开始，沿着一条路径遍历至最深的节点，再返回上一层继续遍历其他未访问过的节点。DFS的过程可以用递归或栈来实现。

在深度优先遍历中，首先访问起始节点，并将该节点标记为已访问。然后，从起始节点出发，依次访问与其相邻且未被访问的节点。当遇到没有未被访问的相邻节点时，返回上一层节点，继续遍历其他未访问的相邻节点，直到所有节点都被访问过为止。

算法实现（递归版本）：
1. 标记当前节点为已访问
2. 遍历当前节点的邻接节点：
    1) 如果邻接节点未被访问，则递归调用DFS函数访问该节点
3. 递归结束后返回

广度优先遍历（BFS）

广度优先遍历是一种按层遍历的方法，即从起始节点开始，先访问其所有相邻节点，然后再逐层访问其他未访问过的节点。BFS的过程可以用队列来实现。

在广度优先遍历中，首先访问起始节点，并将该节点加入队列。然后，从队列中取出一个节点，依次访问其所有相邻且未被访问的节点，并将这些节点加入队列。重复该过程，直到队列为空为止。

算法实现（队列版本）：
1. 将起始节点加入队列
2. 标记起始节点为已访问
3. 循环直到队列为空：
    1) 从队列头部取出一个节点
    2) 遍历该节点的邻接节点：
        如果邻接节点未被访问，则将其加入队列，并标记为已访问

总结

图的遍历是一种重要的算法，用于查找和分析图中的数据。深度优先遍历和广度优先遍历是两种常见的图遍历方式。深度优先遍历通过递归或栈的方式实现，适合用于查找深度层次较深的节点。广度优先遍历通过队列的方式实现，适合用于查找距离起始节点较近的节点。

无论是深度优先遍历还是广度优先遍历，都需要使用一个标记数组来记录节点是否被访问过，以防止重复访问或陷入死循环。在实际应用中，根据具体的问题场景和需求，选择合适的遍历方式可以提高算法的效率和准确性。