抽象数据类型图的定义

《抽象数据类型图的定义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章图7.1抽象数据类型图的定义7.2图的存储表示7.3图的遍历7.4最小生成树7.5重（双）连通图和关节点7.6两点之间的最短路径问题7.7拓扑排序7.8关键路径图是由一个顶点集V和一个弧集R构成的数据结构。Graph=(V,R)其中，VR＝{

2、v,w∈V且P(v,w)}表示从v到w的一条弧，并称w为弧头，v为弧尾。谓词P(v,w)定义了弧的意义或信息。图的结构定义:由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}V

3、R1={,,,,,,}若VR必有VR,则称(v,w)为顶点v和顶点w之间存在一条边。BCADFE由顶点集和边集构成的图称作无向图。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}名词和术语网、子图完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABEC

4、FAEABBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132弧或边带权的图分别称作有向网或无向网。假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图；含有e=n(n-1)条弧的有向图称作有向完全图；若边或弧的个数e

5、点的出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。ABECF如:长度为3的路径{A,B,C,F}简单路径:序列中顶点不重复出现的路径。简单回路:序列中第一个顶点和最后一个顶点相同的路径。若图G中任意

6、两个顶点之间都有路径相通，则称此图为连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。ABECFABECF对有向图，否则，其各个强连通子图称作它的强连通分量。假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFE结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作遍历插入和删除弧

7、基本操作CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&G)://销毁图结构的建立和销毁对顶点的访问操作LocateVex(G,u);//若G中存在顶点u，则返回该顶点在//图中“位置”；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。对邻接点的操作FirstAdjVex(G,v);//返回v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w

8、的）“下一个邻接//点”。若w是v的最后一个邻接点，则//返回“空”。插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G,v,w);//在G中增添弧，若G是无向的，//则还增添对称弧。DeleteArc(&G,v,w);//在G中删除弧，若G是无向的，//则还删除对称弧。遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每//个顶点

9、调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。7.2图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十