图（Graph）
（1）图：和树比起来，这是一种更加复杂的非线性表结构 图中的元素我们就叫作顶点（vertex）。图中的一个顶点可以与任意其他顶点建立连接关系。这种建立的关系叫作边（edge）。顶点的度（degree），就是跟顶点相连接的边的条数。
（2）把这种边有方向的图叫作“有向图”，把边没有方向的图就叫作“无向图”。
（3）入度和出度。顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。
（4）带权图（weighted graph）。在带权图中，每条边都有一个权重（weight），比如我们可以通过这个权重来表示 QQ 好友间的亲密度。
（5）邻接矩阵。图的最直观存储方法。邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j] 和 A[j][i] 标记为 1；对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i][j] 标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i] 标记为 1。对于带权图，数组中就存储相应的权重。
缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。
（6）邻接表（Adjacency List）。有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。
（7）逆邻接表。与邻接表相反。类比，用户关注了谁和被哪些用户关注的情况。
（8）邻接表，改进版本，将邻接表中的链表改为支持快速查找的动态数据结构。红黑树、跳表、有序动态数组还是散列表？大规模数据场景下会涉及到使用哈希算法进行数据分片的做法。
（9）数据表存储。给两列用户id都建立索引。
（10）微信好友。邻接表存储无向图。每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。
深度优先和广度优先搜索算法
（1）图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。
（2）深度优先搜索算法和广度优先搜索算法，既可以用在无向图，也可以用在有向图上。
（3）广度优先搜索（BFS）。直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。
广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。
（4）深度优先搜索（DFS）。最直观的例子就是“走迷宫”。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。
每条边最多会被访问两次，一次是遍历，一次是回退。图上的深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。所以总的空间复杂度就是 O(V)。
（5）结论：这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。
若有收获，就点个赞吧
0 人点赞
