文档介绍：***(V)及顶点间的关系集合E所组成的一种数据结构:Graph=(V,E)其中V={x|x某个数据对象}是顶点的非空有限集合;E={(x,y)|x,yV}//边(Edge)集合或E={<x,y>|x,yV}//弧(Arc)——无向图G是由两个集合V(G)和E(G)组成的其中:V(G)是顶点的非空有限集;E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v) 有向图——有向图G是由两个集合V(G)和E(G)组成的其中:V(G)是顶点的非空有限集;E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为<v,w>,v,w是顶点,v为弧尾(或始点),w为弧头(终点).<v,w><w,v>:V(G2)={1,2,3,4,5,6}E(G2)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例2157324G16图G1:V(G1)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)},即有两类图形不在本章讨论之列:(无向)pletedgraph):n个顶点的有n(n-1)/:n个顶点的有n(n-1)(sparsegraph):边或弧很少的图,通常边数e<nlog2n稠密图(Densegraph):无向图中,边数接近n(n-1)/2;有向图中,弧数接近n(n-1)嫩诫昏颓捉买爷算墨抢潦侮寥告搔奉十频窄贼愚隅竣冈汕像零乍以倔啤硒数据结构DS数据结构DS6有向网权————带权的无向图称为无向网;带权的有向图称为有向网;***尿耳术右暑憾努疵缺数据结构DS数据结构DS7子图——已知图G(V,E)和图G’(V’,E’),若满足:V’V且E’E则称G’(或相邻点),关联:如果e=(u,v)是E(G)中的一条边,则称u与v互为邻接点或相邻点;称边e与顶点u,v关联;如果a=<u,v>是E(G)中的一条弧,则称u邻接到v或v邻接于u,也称弧a与顶点u,(与树中结点的度不同):无向图中,顶点v的度是与该顶点v关联的边数,记作TD(v)有向图中,顶点v的度分成入度与出度入度:以该顶点v为终头的弧的数目,记为ID(v)出度:以该顶点v为始点的弧的数目,记为OD(v)一个顶点v的度等于该顶点的入度与出度之和,即TD(v)=OD(v)+ID(v)