数据结构讲义7VIP免费

1图的定义和术语7

2图的存储结构7

3图的遍历7

4图的连通性问题7

5最短路径第七章图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的一条单向通路,它是有方向的

有向图与无向图在有向图中，顶点对是有序的

在无向图中，顶点对(x,y)是无序的

1图的定义和术语2数据结构ABCDABCDE有向图G1无向图G2•顶点：•有向边（弧）、弧尾或初始结点、弧头或终止结点ABAB•有向图：G1=（V1，{A1}）V1={A,B,C,D}A1={,,,}•顶点：•无向边或边AB•无向图：G2=（V2，{A2}）V2={A,B,C,D,E}A2={(A,B),(A,C),(B,D),(B,E),(C,E),(D,E)}AB37

1图的定义和术语数据结构•完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图

有n个顶点的有向图有n(n-1)条边,则此图为完全有向图

•权某些图的边具有与它相关的数,称之为权

带权图叫做网

1图的定义和术语数据结构•邻接顶点如果(u,v)是E(G)中的一条边，则称u,v互为邻接顶点

•顶点的度顶点v的度是与它相关联的边的条数

记作TD(v)

在有向图中,顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)

5ABCD有向图G1ABCDE无向图G2ID(A)=1;OD(A)=2;ID(B)=1;OD(B)=0;……TD(A)=2;TD(B)=3;TD(C)=2;TD(D)=2;TD(E)=37