1、完全无向图有n(n-1)/2条边，完全有向图有n(n-1)条边。
2、网络=带权图
3、图中任意一对顶点都是连通的，称为连通图。非连通图的极大连通子图叫做连通分量。
4、有向图的每一对顶点都连通则称为强连通图。非强连通图的极大连通子图叫做强连通分量。
5、生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。（连通图）
（1）如果在生成树上添加1条边，必定构成一个环；（2）若图中有n个顶点，却少于n-1条边，必为非连通图。
注：如果一个图n个顶点和小于n-1条边，则是非连通图；如果它多于n-1条边，则一定有环；但是n-1条边，则不一定是生成树。
6、生成森林：由若干生成树组成，含全部顶点，但构成这些树的边是最少的。（非连通图）
7、如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。
一、图的存储结构
1、邻接矩阵（数组）：空间复杂度O(n^2)，多用于稠密图，具有唯一性；
2、邻接表（链式）:空间复杂度O（n+e），多用于稀疏图，邻接表不唯一。
二、图的遍历
设置一辅助数组visited[n]用来标记每个被访问过得顶点，访问过标记为1，否则为0。
1、深度优先遍历DFS
（1）在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1;
（2）再从w1出发，访问与w邻接但还未被访问过得顶点w2;
（3）否则回退。直到所有顶点都被访问。
2、广度优先遍历BFS
（1）在访问了起点v之后，依次访问v的邻接点；
（2）然后再依次访问这些顶点中未被访问过的邻接点；
（3）直到所有顶点都被访问过为止。
时间复杂度 空间复杂度
原文：http://www.cnblogs.com/seven7seven/p/3633190.html