一，图的概述
以前的线性结构是1:1的关系、树形结构是1:n的关系，现在我们要学的图结构就是n:n的关系
一个图一般可以分成三个集合，G、V、E
集合G包含顶点和顶点之间的偶对记为G(V,E)，偶对连接两个顶点称之为边或弧，V集合包含所有顶点，E集合包含所有边或弧
1.图的基本术语
a.简单图：不存在顶点到其自身的边，且一条边不重复出现
b.有向图：边带有方向
c.无向图：边没有方向
d.有向无环图(DAG)：一个有向图，无法经过若干条边回到该顶点，就是有向无环图
上图左边是有环，右边是无环
e.混合图：可能有向，也可能无向
f.完全图：任意两顶点之间都有一条边
完全无向图的边数：n(n-1)/2
完全有向图的边数：n(n-1)
2.点或边的术语
a.端点：若存在一条边(i,j)，则i和j称之为这条边的端点
b.邻接点：i和j互为邻接点
c.入度(in-degree)、出度(out-degree)：指向自己的度、指向别人的度（只在有向图中）
左图11顶点入度有2条，出度有3条
d.子图：上图中5、2、11、19组成的图是整个图的子图
e.回路或环：一条路径的起点和终点为自身
f.欧拉环路：将图中所有边都恰好走过一遍并最终回到自身，也就是路径长度等于边的总长度，如下图{C,A,B,A,D,C,D,B,C}
g.哈密尔顿环路：将所有节点都恰好走过一遍(除了起点和终点){C,A,D,B,C}
h.连通图：如果顶点x、y存在可相互抵达的路径（直接或间接）则称x、y是连通的，如果图G任意两个顶点都是连通的，则称G为连通图，否则就是非连通图
i.无向图G中的极大连通子图称为G的连通分量
连通图只有一个极大连通子图就是其本身，非连通图有多个极大连通子图
之所以称之为极大是因为再添加这个极大连通子图外的原图中的任意顶点或边都会破坏连通性
j.极小连通子图，去除连通子图的任意一条边都会破坏连通性
比如四个节点四条边，去掉一条还是连通的所以不是极小连通子图，如果是四个节点三条边则去掉任意一条边都不会再联通，那么这个连通图就是极小连通子图
k.强连通图和强连通分量
上面不加“强”字都是无向图，而加了强“字”一般都是有向图
在有向图中顶点i和顶点j之间有路径则称两点是连通的
强连通图：任意两顶点i和j都是连通的
强连通分量：原图添加任意顶点都导致这个连通子图不相同
l.稠密图和稀疏图
当一个图接近完全图叫稠密图，反之稀疏图，一般这个临界值为nlogn（n为顶点个数）
j.权和网
图中每一条边可以附一个值，这个值称为权，可以表示两顶点的距离或相互抵达的代价
边上有权的图称为带权图或网
k.连通图的生成树：一个极小连通子图含有图中的所有n个顶点，但是只有构成树的n-1条边
二、图的存储
1.邻接矩阵
提到矩阵我们应该想到二维数组，其用处是存储边，当两顶点连通可以记录为1否则0
2.对称邻接矩阵
也就是无向图，一个顶点连通另一顶点，说明另一顶点也连通这个顶点
3.有向邻接矩阵
4.带权邻接矩阵
两顶点连通记录这条边的权值
5.无向邻接表
6.有向邻接表
对应的链表上存储的是出度，找某点指向的点容易，找所有指向自己的点效率低
7.带权邻接表
链表节点多一个区域存储权值
8.逆邻接表
对应点链表上存储的是入度，找所有出度效率低
