图的深度优先遍历和广度优先遍历

转自：https://www.cnblogs.com/nr-zhang/p/11236369.html

 

深度优先遍历简称DFS（Depth First Search），广度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种方式。

 

我们来到一个游乐场，游乐场里有11个景点。我们从景点0开始，要玩遍游乐场的所有景点，可以有什么样的游玩次序呢？

深度优先遍历

二叉树的前序、中序、后序遍历，本质上也可以认为是深度优先遍历。

第一种是一头扎到底的玩法。我们选择一条支路，尽可能不断地深入，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入。

 

在图中，我们首先选择景点1的这条路，继续深入到景点4、景点5、景点3、景点6，终于发现走不动了（景点旁边的数字代表探索次序）：

于是，我们退回到景点1，然后探索景点7，景点8，又走到了死胡同。于是，退回到景点7，探索景点10：

  

按照这个思路，我们再退回到景点1，探索景点9,最后再退回到景点0，后续依次探索景点2，终于玩遍了整个游乐场：

广度优先遍历

二叉树的层序遍历，本质上也可以认为是深度优先遍历。

在图中，我们首先探索景点0的相邻景点1、2、3、4

接着，我们探索与景点0相隔一层的景点7、9、5、6：

最后，我们探索与景点0相隔两层的景点8、10：