图

概念

1. vertex 顶点
2. edge 边
3. 无向图
4. 有向图(单向)
5. 权，边上的值
   1. 向和权可以排列组合
6. 点的邻边
7. 路径
8. 环，能从一个点回到自己
   1. 有环图
   2. 无环图
      1. 树是一种无环图
      2. 但是无环图不是树，比如图中有多个联通分量
9. 自环边
   1. 自己和自己有一条边
10. 平行边
    1. 两个顶点之间有两条边
11. 简单图
    1. 没有自环边和平行边
12. 联通分量
    1. 两个分量之间没有边联合，但是他们属于一个图
13. 联通图的生成树
    1. 连通图才有生成树
    2. 该树也是联通的，边为 vertex - 1
    3. 该树包含所有的顶点
14. 一个图如果有多个联通分量
    1. 各个联通分量可以有生成树
    2. 整个图就有生成森林
15. 顶点的度 degree
    1. 无向无全权图，则 vertext 的 degree 就是他的邻边数

表示

简单图

无向无权图

1. 使用邻接矩阵
2. A[i][j] = 1 表示两个点相邻
3. 简单图没有自环，所以邻接矩阵的主对角线都为0