数据结构7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5最短路径第七章图1数据结构•图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,yV}或E={
|x,yV&&Path(x,y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条单向通路,它是有方向的。有向图与无向图在有向图中，顶点对是有序的。在无向图中，顶点对(x,y)是无序的。7.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)条边,则此图为完全有向图。•权某些图的边具有与它相关的数,称之为权。带权图叫做网。47.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.1图的定义和术语数据结构•子图设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称图G’是图G的子图。67.1图的定义和术语数据结构•路径在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。•简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。77.1图的定义和术语数据结构•回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。•路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。87.1图的定义和术语数据结构•连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。ABCDEFGIJLHMKABCDEHMFGIJLK无向图G无向图G的三个连通分量97.1图的定义和术语数据结构•强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。有向图G有向图G的两个强连通分量ABCDABCD107.1图的定义和术语数据结构生成树一个连通图的生成树是它的极小连通子图，包含连通图的全部n个顶点，但只有构成一棵树的n-1条边。ABCDEHMABCDEHM无向图G无向图G的生成树117.1图的定义和术语数据结构CreatGraph(&G,V,VR);//按定义(V,VR)构造图DestroyGraph(&G);//销毁图•结构的建立和销毁图的基本操作•对顶点的访问操作LocateVex(G,u);//若G中存在顶点u，则返回该顶点在//图中“位置”；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。127.1图的定义和术语数据结构FirstAdjVex(G,v);//返回v的“第一个邻接点”。若该//顶点在G中没有邻接点，则返回空。NextAdjVex(G,v,w);//返回v相对于w的“下一个邻//接点”。若w是v的最后一个邻接点，则返回“空”。•对邻接点的操作InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。•插入或删除顶点137.1图的定义和术语数据结构InsertArc(&G,v,w);//在G中增添弧DeleteArc(&G,v,w);//在G中删除弧•插入和删除弧DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每个顶点调用函数//Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历...
