1、图的基本概念G=(V,E)
树中的元素我们称为节点，图中的元素我们就叫做顶点。一个图就是一些顶点（V）的集合，顶点有时也称为节点或者交点，这些顶点通过一系列边(E)连接，跟顶点相连接的边的条数叫做度。引入边的“方向”，就是有向图，在有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。例顶点2的入度为2，出度为2。每条边都有一个权重（weight）的图就是带权图。而这种带权的图被称为网。此图为非连通图，若顶点0和1有边连接，则为连通图。
树和链表也属于图。常见的我们的qq，微博互关，微信好友等都是图的应用。
2、图的存储
图的两个主要的存储方式：邻接矩阵和邻接表。
邻接列表：
在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。邻接列表只描述了指向外部的边。
当链表过长，考虑转成其他数据结构处理，如红黑树、跳表、散列表等加快查询效率，查找两个顶点之间是否存在边。
邻接矩阵：
在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。但是这种方式往图中添加顶点的成本非常昂贵，因为新的矩阵结果必须重新按照新的行/列创建，然后将已有的数据复制到新的矩阵中。
优点：存储方式简单，直接、方便计算；
缺点：浪费存储空间；
3、图的遍历
图的最基本的两种搜索算法：广度优先搜索（Breadth-First-Search）和深度优先搜索（Depth-First-Search）。
因为图中的任意顶点都可能与其他顶点相邻，所以在图的遍历中必须记录已被访问的顶点，避免重复访问,所有顶点只访问一次。
1）广度优先搜索：
广度优先搜索类似于树的层次遍历过程。即先查找离起始顶点最近的，然后是次近的，依次往外搜索。它需要借助一个队列来实现。
准备几个重要的辅助变量 visited数组、queue队列。
visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 v2 被访问，那相应的 visited[2]会被设置为 true。
queue 是一个队列，用来存放每一层的顶点；
思路：
1、初始时全部顶点均未被访问，visited数组初始化为0，队列中没有元素。|visited|0|0|0|0|0|0|
2、访问顶点v0，并置visited[0]的值为true，同时将v0入队。
3、将v0出队，访问v0的邻接点v2。首先判断visited[2]，因为visited[2]的值为false未访问过，则访问v2。访问完将visited[2]置为true，并将v2入队。|visited|1|0|1|0|0|0|
3、同样操作访问v0邻接点v1、v3。分别将v1、v3入队列，标识设置成已访问过，|visited|1|1|1|1|0|0|
至此，v0的全部邻接点均已被访问完毕，（即第一层访问完毕），元素均已入队列，已访问标识visited[0]、visited[1]、visited[2]、visited[3]均为true已访问。
4、因为v0的全部邻接点均已被访问完毕，将队头元素v2出队（开始第二层的遍历），开始访问v2的所有邻接点。
继续访问v2邻接点v4，判断visited[4]，因为其值为0，访问v4，将visited[4]置为1，并将v4入队。
5、v2的全部邻接点均已被访问完毕。将队头元素v1出队，开始访问v1的所有邻接点。继续访问v1邻接点v4，因为visited[4]的值为1，访问过了，不进行访问。继续访问v1邻接点v5，因为visited[5]值为0，访问v5，将visited[5]置为1，并将v5入队。
6、v1访问完，要访问v3了，将v3出列，开始访问v3,发现v5已经访问过了，不在访问。
7、v3的全部邻接点均已被访问完毕，开始访问v4的所有邻接点，所以将队头元素v4出队。将visited[6]值为1，并将v6入队。同理v4的所有邻接点访问完了，访问v5，将v5出列，visited[6]值为1，所以不再访问。
8、继续访问v6邻接点，v6出列，因为visited[4]、visited[5]的值文1，不进行访问。
9、此时队列为空，退出循环，全部顶点均访问完毕。
小结：从v0出发，遍历临接点，入队列。当上一个顶点v0的临接点（v2、v1、v3）全部遍历完，将要访问下一个顶点v2时，将该顶点v2出队列，将当前访问的顶点的临接点继续入队(v4)，当然入队前需要通过visited数组标识判断是否已经访问过，未访问过才入队，依次重复，直到队列为空，遍历结束。实际上，这样求得的路径就是从 v0 到 v6 的最短路径。
那么广度优先搜索的时间、空间复杂度是多少呢？
最坏情况下，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(顶点个数+边个数)，对于一个连通图来说，边数肯定要大于等于顶点数，所以，广度优先搜索的时间复杂度也可以简写为 O(边数)。空间消耗主要在几个辅助变量 visited 数组、queue 队列、但是他们存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(顶点个数)。
2）深度优先搜索：
实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程，非常适合用递归来实现。深度优先搜索类似于树的先序遍历。
依然准备几个重要的辅助变量 visited数组
visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 v2 被访问，那相应的 visited[2]会被设置为 true。
栈 使用栈存储访问的路径信息。
思路：
1、初始时全部顶点均未被访问，visited数组初始化为0。|visited|0|0|0|0|0|0|
2、访问v0，并将visited[0]的值置为1。
3、访问v0的邻接点v2，判断visited[2]，因其值为0，访问v2。将visited[2]置为1。
4、访问v2的邻接点v0，判断visited[0]，其值为1，不访问。
继续访问v2的邻接点v4，判断visited[4]，其值为0，访问v4。将visited[4]置为1。
5、访问v4的邻接点v1，判断visited[1]，其值为0，访问v1。将visited[1]置为1。
6、访问v1的邻接点v0，判断visited[0]，其值为1，不访问。
继续访问v1的邻接点v4，判断visited[4]，其值为1，不访问。
继续访问v1的邻接点v5，判读visited[5]，其值为0，访问v5。将visited[5]置为1。
7、访问v5的邻接点v1，判断visited[1]，其值为1，不访问。
继续访问v5的邻接点v3，判断visited[3]，其值为0，访问v3。将visited[3]置为1。
8、访问v3的邻接点v0，判断visited[0]，其值为1，不访问。
继续访问v3的邻接点v5，判断visited[5]，其值为1，不访问。
v3所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5所有邻接点。
9、访问v5的邻接点v6，判断visited[6]，其值为0，访问v6。将visited[6]置为1。
访问v6的邻接点v4，判断visited[4]，其值为1，不访问。
访问v6的邻接点v5，判断visited[5]，其值为1，不访问。
v6所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5剩余邻接点。依次类推回溯到0，发现都遍历过了结束。
小结：从v0出发，依次遍历临接点，入栈v0 、v2 、v4 、v1、 v5 、v3。到v3发现临节点全部遍历完，开始回溯（将v3出栈）到他的上一个顶点（v5），继而遍历v6,然后发现v6的临节点全部遍历完（将v6出栈），此时栈顶指针指向V5，同理进行判断回溯，依次出栈V1、V4 、V2、 V0。直至栈为空，遍历结束。深度优先搜索相当于两个过程，一个深度遍历和一个回溯过程，每个边最多会走两次。遍历新的节点时，入栈，当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作。
深度优先搜索的时间、空间复杂度是多少呢？
可以看出，每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的==深度优先搜索算法的时间复杂度是 O(边的个数）。
深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。递归调用栈的最大深度不会超过顶点的个数，所以==总的空间复杂度就是 O(顶点的个数)。
