图的遍历

0x00 深度优先 dfs

​ 由于dfs会将每个顶点都遍历，这是第一部分，第二部分，就是找到v的每个邻接点所占用的时间复杂度。对于用邻接矩阵储存的图，其dfs时间复杂度是：每个节点都会遍历一次，而每次找到邻接点，都需要遍历对应节点的一整行，找到非零项，所以时间复杂为O(n^2)。

​ 而邻接表储存，每个点都访问一次，另外，在扩展节点时，会访问链表，链表总长度是边数的两倍，所以时间复杂度是O(N+2*E)->O(N+E)

0x01 广度优先 bfs

​ 实际上，如果将每次扩展的节点当作当前节点的儿子节点，会得到一棵树，dfs则是对该树的先序遍历，而bfs则是层序遍历。

​ 为什么要是用两种遍历顺序，因为两种遍历顺序各有优点，dfs适合目标离起点较远的情况，bfs相反