BFS
算法概述：
创建一个空队列。从某个点开始，找到该点所指向的所有的点并且没有被标记过的，放入队列中，并且对当前的点做标记，表示被遍历过了。再从队列中取出新的点，重复前面的操作。直到队列为空。
由于图不一定是连通的，需要遍历1~n个点。
要点：
BFS类似于树的层次遍历，由于存储的边的顺序可能不同，遍历次序也不同。（邻接表是不同，邻接矩阵是相同的）
空间复杂度分析：
不管是邻接表还是邻接矩阵，都需要一个辅助队列来存储的放入的点，在最坏情况下，是O(V)，即一次存下所有的点
时间复杂度分析：
对于邻接表：每个点都是要被搜索一遍，复杂度为O(n)，对于每个点，都要遍历相连的边，由于是邻接表，可以用O(E)走了所有的边。总复杂度为O(E+V)
对于邻接矩阵：每个点仍需要搜索一遍，复杂度为O(n)，对于每个点，搜索相连的边，都需要O(n)的复杂度，（相当于遍历了一个邻接矩阵）故复杂度为O(n^2)
应用：
1、可以用BFS算法来求解单源最短路问题，该图必须得是非带权图，根据BFS算法的特性，从一个点向外扩散，到某个点肯定是最近距离。
2、相应的BFS搜索可以生成广度优先生成树，根据遍历的顺序来确定。对于邻接矩阵的来说，一个给定的图的邻接矩阵唯一，生成树也唯一。对于邻接表来说，由于存储相连点的顺序不同，生成树不唯一。
如果该图不是连通的，生成的是森林。
DFS
算法概述：
类似于先序遍历，从某个点开始，一直递归相邻的点，每遍历到一个点，标记并直接输出，表示遍历过了。到底了再退回到上几步。
由于图不一定联通，同样需要遍历1~n。
要点：
类似于树的先序遍历，遍历的出的顺序，邻接表是不同，邻接矩阵是相同的。
时空复杂度分析：
在递归的时候需要一个栈来存储遍历的点，最坏情况下是O(n)
时间复杂度分析：
和BFS分析相同
应用：
遍历得到对应的生成树。相应的，如果是连通，是树，不然就是森林
标签：遍历,复杂度,邻接矩阵,生成,BFS,邻接,408 From： https://www.cnblogs.com/yxdsTutorial/p/17379245.html