一、图(graph)是一种更为复杂的数据结构，结点之间的关系是任意的，图中任意两个数据元素之间都可能有关。
1. 图的顶点Vertex
2. 图的边(弧Arc),无向的(v,w),边edge，有向的<v->w v:弧尾tail,w:弧头head>
3. 关系的集合，顶点的集合，操作的集合
4. 完全图:n个顶点的无向图有n(n-1)/2条边；有向图n(n-1)条弧称做有向完全图
5. 稀疏图:e<nlogn,稠密图e>nlogn
6. 权值:weight,边的度量,带权的图称为网(network)
7. 子图
8. 出度(out):v定点发出的弧数量
9. 入度(in):w定点汇聚的弧数量
10. 路径：从a->z的顶点序列,有路径是联通的
11. 连通图：任意两个点之间都有路径
12. 连通分量：无向图中的极大连通子图
13. 强连通图，强连通分量
14. 一个连通图的生成树是一个极小连通子图，含有图中全部顶点，但只有足以构成一棵树但n-1条边
15. 一个有向图的生成森林是由若干棵有向树组成的。
二、图的存储结构:
1. 数组表示法
2. 邻接表：链式存储结构
3. 十字链表：链式存储结构
4. 邻接多重表
三、图的遍历：
1. 从图的某一个顶点触发访遍途中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历.
2. 深度优先搜索:类似树的先序遍历
3. 广度优先搜索:类似树的层次遍历
四、图的连通性问题
1. 无向图的连通分量和生成树
2. 有向图的强连通分量
3. 最小生成树：光缆铺设城市线路问题
4. 关节点和重连通分量
五、有向无环图及其应用DAG
1. 表达式求值
2. 拓扑排序
3. 关键路径
六、最短路径问题