图的遍历有哪两种方式

图的遍历是指按照一定的规则，依次访问图中的所有顶点，从而得到图的完整信息的过程。图的遍历有两种方式：深度优先遍历和广度优先遍历。本文将从算法角度和应用场景角度两个角度来分析这两种遍历方式。

一、算法角度

1.深度优先遍历

深度优先遍历（Depth First Search，简称DFS）是一种经典的图遍历算法。它顾名思义是优先往深度走，是一种先序遍历。其基本思想是从图的某一源点出发，就从该点开始沿着一条路走直到走到末端，然后返回到上一个顶点，再走另一条路，知道遍历完整个图。由于深度优先遍历是递归的形式，其空间复杂度与递归深度有关，因此容易发生栈溢出等问题。

2.广度优先遍历

广度优先遍历（Breadth First Search，简称BFS）是另一种经典的图遍历算法。它的基本思想是从图的某一源点开始，先遍历该点的所有邻接点，再遍历它们的邻接点，以此类推，直至遍历完整个图。广度优先遍历是一种层次性遍历算法，可用队列实现。和深度优先遍历不同，它不是递归形式，它的空间复杂度取决于队列中的元素数目。

二、应用场景

1.深度优先遍历

深度优先遍历在很多算法实现中都得到了广泛运用，如寻找连通块和欧拉路径等。其中一个重要的应用场景是迷宫寻路。假设一个给定的迷宫是用一个矩阵来表示的，其中0表示可以通过的通路，1表示障碍物，可以给定一个起点和一个终点，需要用深度优先遍历寻找一条从起点到终点的路径。因为深度优先遍历可以占用至多O(n^2)的空间，因此它适用于小迷宫。

2.广度优先遍历

广度优先遍历的应用场景也很多。例如在社交网络中，可以用广度优先遍历来寻找一个人的朋友或者确定两个人之间的最短路径；在自然语言处理中，可以用广度优先遍历搜索词汇表来寻找同义词，或者用它来在语法树等结构中搜索路径等。此外，广度优先遍历的时间复杂度为O(n)，因此它适用于大型图的遍历。