图是什么
图的核心部分是顶点，顶点之间的关系是由边来表示的，所以可以衍生出无向图和有向图，然后根据边的性质又可以衍生出加权和不加权，最后整体又可以衍生出强连通，连通和不连通
所以图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)
无向图
顶点之间的边没有方向，也就是顶点A和顶点B之间存在一条边，那么A能到B，B能到A；
那么无向图就是由这种边的关系组成的
性质：
- 在无向图中，如果任意两个顶点都存在边，那么边的总数为 $\frac{n(n-1)}{2}$
有向图
顶点之间的边存在方向，那么该边称为弧或者有向边，如果顶点A和顶点B之间存在一条从A指向B的弧，那么A能到B，B不能到A
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则该弧为有向完全图，含有$n(n-1)$条边
弧
<A,D>表示弧，表示顶点A到顶点D之间存在一条从A指向D的有向边，A是弧尾，D是弧头，也就是弧指向的是弧头
网
网也就是带权的图，权表示一个顶点到另一个顶点的代价
度（TD）
对于无向图中，度表示一个顶点拥有边的条数，假设一个顶点有三条边关联，那么该顶点的度为3
边数是顶点度数和的一半
入度（ID）与出度（OD）
入度和出度是针对有向图说的，入度是以该顶点为弧头的，出度是以该顶点为弧尾的
TD = ID + OD
无向图度数等于边数的两倍
有向图的度数（入度+出度）等于两倍的边数，且有多少入度就有多少出度
图的数据结构
临接矩阵
一个图如果有n个节点，那么临接矩阵的大小是n*n的二维矩阵，对于(i,j)的值不为0，表示顶点i能够到j
邻接表
邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。
对于数组中的一个元素，对应一个链表，表示该元素中指向链表中对应的所有节点
深度优先搜索
深度优先搜索是认准一个方向进行遍历，直到在这个方向到头了才会停止，停止后会回溯到上一层节点，从上一层的后面节点进行深度搜索，直到所有节点都被访问
DFS框架
- 确认递归函数的返回值和参数
- 确认递归终止条件
- 处理当前节点的方法
广度优先搜索
广度优先搜索是基于起点位置开始，向四周扩散的算法，主要用于解决两点之间最短路径问题
BFS框架
- 定义队列和四个方向
- 将起始位置放入队列，并且标记为已经使用
- 开始遍历放入队列中
- 当遍历到终点，该路径为最短路径