1.图的概念
（1）简略图：无反复边且没有顶点到本身的边（数据结构都是简略图）
（2）度：无向图为附丽该点的边数，有向图为出度和入度的和
（3）简略门路：两头顶点不反复的门路
（4）对于无向图，为连通和连通图；对于有向图，为强连通和强连通图
（5）对于n个顶点的图：为无向图，为连通则起码n-1条边，不为连通最多Cn-1(2)条边
为有向图，为强连通，则起码n条边（6）极大连通子图：（1）为无向图中，子图必须连通且蕴含尽可能多的点和边
（2）为有向图中，子图必须强连通且蕴含尽可能多的点和边（7）连通重量和强连通重量：无向图的极大连通子图和有向图的极大连通子图
（8）无向连通图的生成树：为蕴含所有点的极小连通子图（即蕴含所有点且边尽可能少）（n个点则有n-1条边）
（9）无向/有向齐全图：任意两个点有边/任意两个点存在方向相同的两条弧
2.图的存储
（1）邻接矩阵法：
无向图：第i个节点的度：某行（列）的非零元素的个数
有向图：第i节点的出度：第i行的非零元素的个数
求度，出度，入度的工夫复杂度：O(v) 工夫复杂度：O(v*2)
适宜存储浓密图
性质：
(2)邻接表法
性质：街坊表法示意不惟一，但矩阵是惟一的，适宜存储稠密图
（3）十字链表法（只存储有向图）
（4）邻接多重表
总结：
3.图的利用
（1）最小生成树：带权连通图的权值之和最小的生成树
Prim算法：不停的加顶点（O(v平方),适宜边稠图）
Krusal算法：不停选最小的边，使边两边的点连通（O(elog2e),适宜边疏图）
（2）最短门路
（3）有向无环图
（4）拓扑排序
性质:(1)拓扑和逆拓扑可能不惟一
（2）拓扑和逆拓扑内不能有环（5）要害门路（性质，办法可突击）