前言
图建构好后，针对具体的问题，我们常常需要通盘的读取图中的信息，包括顶点（vertex）和边（edge），以及它们之间的关系。这种读取图中所有信息的方法就是图的遍历（traversal），也称为搜索（search），就是从图中某个顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次。遍历是很多图论算法的基础。
遍历需要决定从哪里开始读，依照什么顺序读，要读到哪里为止。如果遍历方法与需解决问题结合的好，甚至还可以一边读取图的信息，一边顺手解决问题！
一、图的遍历
1.1 图和树的遍历
树的遍历是从根节点开始的，由于每个节点都只有一个双亲，因此其遍历还是相对简单的。而图的遍历则可以选择从任意一个节点开始，同时图中每一个节点都可能与其余的节点相邻接，不可避免的会多次访问同一个节点，因此在遍历的过程中需要将已访问的节点打上标记，以避免重复。
图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：
- ① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
- ② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
- ③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
- ④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
1.2 遍历的方法
遍历有2个著名的方法：深度优先搜索（DFS, depth first search）和广度优先搜索（BFS, breadth first search）。
以上图的中国公路网为例，我们从北京出发，采用怎样的遍历方法访问所有的城市呢？
广度优先就是从北京出发，先访问那些直接与北京相连的城市，比如天津、沈阳、包头、太原、郑州、济南等；然后再访问那些城市和这些已访问过的城市相连，如长春与沈阳相连，武汉与郑州相连，南京与济南相连等。而后再访问与长春、武汉、南京等相连的城市，如哈尔滨、上海等，直到把所有的城市都访问一遍为止。
深度优先就是从北京出发，随便找一个相连的城市，如济南，作为访问的城市，然后从济南出发，随便找一个与济南相连的城市，比如南京，再从南京出发，随便找一个与南京相连的城市，如上海，一直找到头，直到找不到城市，再往回找。因为一条路“走到黑”，所以叫深度优先。
这两种方法都可以保证访问到全部的城市。当然，前面也提到过，不论采用何种方法，都应该记录下已访问的城市，避免重复访问或遗漏。
1.3 遍历的时间复杂度
关于图遍历的时间复杂度。对于一个图来说，不管我们使用什么样的图存储结构和搜索方法，该图中的各个顶点(vertex)和各条边(edge)都是必须要搜索到的。因此，遍历一个图的时间复杂度至少是O(V+E)级别的，V，E分别表示顶点和边的数量。
当然，这里的遍历指的是用来访问图中每个节点的。但有时候，我们其实只需要寻找某个特定节点或某一类节点，对于这种搜索，我们也可以通过设计高效的算法来大大提高搜索效率。
参考：
https://blog.csdn.net/saltriver/article/details/54428796
https://baike.baidu.com/item/%E5%9B%BE%E9%81%8D%E5%8E%86/6590947
网友评论