1 7.1图的基本概念图的定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E )其中V = { x " x某个数据对象}是顶点的有穷非空集合； E = {(x, y) " x, y V }或E = { " x, y V && Path (x, y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从x到y的一条通路。第1页/共72页ACM培训资料数据结构与算法全文共72页，当前为第1页。 2有向图与无向图完全图第2页/共72页ACM培训资料数据结构与算法全文共72页，当前为第2页。 3邻接顶点如果(u, v)是E(G)中的一条边，则称u与v互为邻接顶点。子图设有两个图G＝(V, E)和G'＝(V', E'),若V ' V且E' E,则称图G'是图G的子图。第3页/共72页ACM培训资料数据结构与算法全文共72页，当前为第3页。 4顶点的度一个顶点v的度是与它相关联的边的条数，记作TD(v)。顶点v的入度是以v为终点(弧头)的有向边的条数,记作ID(v);顶点v的出度是以v为始点(弧尾)的有向边的条数,记作OD(v)。路径在图G＝(V, E)中,若从顶点vi出发,沿一些边经过一些顶点vp1, vp2, …, vpm，到达