一、图的基本概念
（一）图的点和边
1、图的定义：一个图G=（V,E）由顶点集V和边集E组成。
2、边：一个点对（v,w），分为有向边，和无向边；
3、图的分类：有向图（点对是有序的），无向图（点对是无向的）
4、点与边的关系：顶点v与w邻接，当且仅当（v,w）属于E
5、权：每条边除了有顶点（v,w）有时还有自己的值或权。
（二）图的路径
1、路径定义：图的路径是一个顶点序列w1,w2,w3,……,wn，使得（wi，wi+1）属于E，（1<=i<n）
2、路径的长：
（1）无权路的路径的长度是该路径上的长度
（2）有权路径的路径的长度是该路径上所有边的权值之和
3、环：一个从顶点到它自身的边（v,v），环的长度是1
4、简单路径：一条路径上所有顶点都是互异的，（但第一个和最后一个可能相同）。
（三）圈
1、有向图的圈满足w1=wn且长度至少为1的一条路径，且每条边都是互异的
（eg：无向图的（u，v，u）不是圈，因为（u，v）和（v,u）是同一条边）
2、一个无圈图称为DAG
（四）连通图
1、（无向图）连通：如果一个无向图图的每一个顶点到其他顶点都有一条路径，就称这个图是连通图
2、有向图：
（1）强连通图：一个有向图的每一个顶点到其他顶点都有一条路径，这个图就是强连通的
（2）弱连通图：一个有向图不是强连通涂，但是去掉方向的这个无向图是连通图。