- 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为:G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
- 图中数据元素叫顶点。图中不允许没有顶点，若V为顶点，强调v有穷非空
- 任意顶点都可能有关系，之前的逻辑关系用边来表示
- n个顶点无相完全图有{n*(n-1)}/2条边
- 有相完全图有{n*(n-1)}条边
- 对于具有n个顶点和e条边数的图，无向图0≤e≤n(n-1）/2，有向图0≤e≤n（n-1）
- 一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多于n-1边条，必定构成一个环。有n-1条边并不一定是生成树
- 一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
邻接表小结
◆ 设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。
◆ 在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数。
◆ 在有向图中，第i个链表中的结点个数只是顶点vi的出度。在逆邻接表中的第i个链表中的结点个数为vi的入度。
◆ 建立邻接表的时间复杂度为O(n+e)。