数据结构 图精讲课件.ppt

《数据结构 图精讲课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径图的定义和术语图:用G=(V,E)来表示.V:表示顶点有限集合E:由顶点对表示边的集合有向图:图中边有方向的图无向图:图中边无方向的图如图:V1V4V3V2G1V5V4V3V2V1G2G1为有向图G2为无向图G1有向图G1=(V1,{A1})其中：V1={v1,v2,v3,v4}A1={,,,}G2无向图G2=(V2,{E2})其中V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v

2、1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}我们用n表示图中顶点数目，用e表示边或弧得数目。对于无向图，e得取值范围为0到1/2n(n-1).对于有向图，e得取值范围为0到n(n-1).基本概念在图中的数据元素通常称为顶点,V是顶点的有穷非空集合;E是两个顶点之间的关系的集合.若∈E,则表示从v到w的一条弧,且称v为弧尾或初始点,称w为弧头或终端点完全图：有n(n-1)/2条边的无向图有向完全图：具有n(n-1)条弧的有向图稀疏图:有很少条边或弧（如e

3、与它相关的数，这种与图的边或弧相关的数叫权子图：设有两个图G=(V,{E})和G’=(V’,{E’}),如果V’来自V且E’来自E，则称G’为G的子图例：下图是G1图的子图例子V1V4V3V2V1V3V4V1V3V1度:顶点v的度(Degree)是和v相关联的边的数目，记为TD(V)入度:以顶点v为头的弧的数目称为v的入度,记为ID(v)出度:以顶点v为尾的弧的数目称为v的出度,记为OD(v)TD(v)=ID(v)+OD(v)一般地，如果顶点vi的度记为TD(vi),那么一个有n个顶点，e条边或弧的图，满足如下关系e=1/2∑i=1nTD(vi)连通图:在无向图G中，

4、如果从顶点v到顶点v’有路径，则称v到v’是连通的;如果对于图中任意两个顶点都是连通的，则称G是连通图连通分量：无向图中的极大连通子图强连通图：在有向图G中，如果对于每一vi,vj∈V,vi!=vj,从vi到vj和从vj到vi都存在路径，则称G是强连通图强连通分量：有向图中的极大强连通子图图的基本操作creatGraph(&G,V,VR);初始条件：v是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图。DestroyGraph(&G);初始条件：图G存在。操作结果：销毁图G。Locatevex(G,u);初始条件：图G存在，u和G中顶点有相同特征。操作

5、结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。GetVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。FirstAdjvex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回空。NextAdjvex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接顶点，则返回

6、空。InsertVex(&G,v);初始条件：图G存在，v是G中某个顶点。操作结果：在图G中增添新的顶点v。DeleteVex(&G,v);初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧，若G是无向的，则还增添对称弧DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的，则还删除对称弧DFSTraverse(G,v,visit());初始条件

7、：图G存在，v是G中某个顶点，visit是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并且对每个顶点调用函数visit一次而且仅一次。一旦visit（）失败，则操作失败。BFSTraverse(G,v,visit());初始条件：图G存在，v是G中某个顶点，visit是顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并且对每个顶点调用函数visit一次而且仅一次。一旦visit（）失败，则操作失败。7.2图的存储结构一：数组表示法(邻接矩阵)用两个数组分别存储数据元素(顶点)d的信息和数据元素之间的关系(边或弧)的信息（邻接矩阵）设：图