# 4. 图的实现和特性
# 定义
图是由顶点和边组成(可以无边，但至少包含一个顶点)
# 图的特性
图可以分为有向图和无向图，在图中：
- (v, w) 表示无向边，即 v 和 w 是互通的
- <v, w> 表示有向边，该边始于 v，终于 w
图可以分为有权图和无权图：
- 有权图：每条边具有一定的权重(weight)，通常是一个数字
- 无权图：每条边均没有权重，也可以理解为权为 1
图又可以分为连通图和非连通图：
- 连通图：所有的点都有路径相连
- 非连通图：存在某两个点没有路径相连
图中的顶点有度的概念：
- 度(Degree)：所有与它连接点的边数之和
- 入度(Indegree)：存在于有向图中，所有接入该点的边数之和
- 出度(Outdegree)：存在于有向图中，所有接出该点的边数之和
# 图的表示方法
图在程序中的表示一般有两种方式：
- 邻接矩阵：
- 在 n 个顶点的图需要有一个 n × n 大小的矩阵
- 在一个无权图中，矩阵坐标中每个位置值为 1 代表两个点是相连的，0 表示两点是不相连的
- 在一个有权图中，矩阵坐标中每个位置值代表该两点之间的权重，0 表示该两点不相连
- 在无向图中，邻接矩阵关于对角线相等
- 邻接链表：
- 对于每个点，存储着一个链表，用来指向所有与该点直接相连的点
- 对于有权图来说，链表中元素值对应着权重
例如在无向无权图中：
在无向有权图中:
而在有向无权图中：
# 图算法
DFS
BFS
待更新...