图的2种常见的遍历形式

在计算机科学领域，图被广泛应用于网络、社交媒体、电路等领域。在图上进行各种操作时，遍历是其中最基本而重要的操作之一。遍历是指在图形中实现从一个顶点到另一个顶点的搜索路径。在图上进行遍历有两种最常见的形式：深度优先遍历和广度优先遍历。本文将从不同角度分析这两种遍历形式的原理、实现和应用。

1. 原理

深度优先遍历和广度优先遍历在遍历图时使用的搜索策略不同。深度优先遍历从初始顶点开始，不断沿着深度方向遍历至最深处，直到所有节点都被访问过。可以使用栈来实现深度优先遍历，每当遍历到一个节点时，将其push进栈中，当该节点的所有相邻节点都访问完后，将其pop出栈继续遍历。这种遍历方法的缺点是可能会陷入死循环，需要额外的判断来避免。

广度优先遍历是按照层次逐步完成的。从初始顶点开始，访问其所有相邻节点，然后再访问这些相邻节点的所有相邻节点，直到所有节点都访问完成。可以使用队列来实现广度优先遍历，类似于宽度优先搜索的思路。需要一个visited数组来标记哪些节点已经被访问过，以避免重复访问。

2. 实现

实现深度优先遍历和广度优先遍历的关键是如何表示图。常见的图表达方式有邻接矩阵和邻接表两种。

邻接矩阵是一个二维数组，其中数组的行和列表示所有节点，如果两个节点之间有边相连，则在对应的矩阵位置标记为1，否则标记为0。在邻接矩阵中查询两个节点是否有边相连的时间复杂度是O(1)，但是如果图稀疏，则矩阵中大部分内容都是0，浪费了大量的空间。

邻接表是一个不规则的二维数组，每个节点对应一个链表，链表中存储该节点所相邻的其它节点。邻接表对于稀疏图的空间利用率更高，但是查询两个节点是否有边相连的时间复杂度则取决于邻接节点的数量。

在实现算法时，可以利用递归来实现深度优先遍历，或者使用栈来实现。同时，可以利用队列来实现广度优先遍历。

3. 应用

深度优先遍历和广度优先遍历都有着广泛的应用。深度优先遍历可以被用于追踪一个状态的历史或路径，比如在游戏或迷宫中寻找最短路径。广度优先遍历可以被用于寻找最短路径和拓扑排序，拓扑排序是指将有向无环图中的节点按照依赖关系排序。

此外，深度优先遍历和广度优先遍历也可以用于判断图中是否存在环。在深度优先遍历中，如果返回到之前访问过的节点，则说明有环；在广度优先遍历中，如果图中有环，则必然存在一个节点被访问过两次。