资源描述：
《【精品数据结构】图3.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第7章图7.1图的定义、术语和基本运算7.2图的存储结构7.3图的遍历与拓扑排序7.4最小生成树7.5最短路径7.6本章小结7.1图的定义、术语 和基本运算7.1.1图的定义及术语图结构的形式化定义：Graph=(V,R)，其中：V={x
2、xD,D是具有相同特性的数据元素的集合}；R={Edge}，Edge={
3、P(x,y)(x,yV),谓词P(x,y)定义了弧上的意义或信息}。圆圈代表数据元素圆圈之间的连线代表数据元素之间的关系在图结构中，一个元素可以有多个直接后继，也可以有多个直接前趋。相关术语顶点（vertex）Edge是两个顶点之间的关系的集合：
4、Edge，则为从x到y的一条弧；x为弧尾或始点；y为弧头或终点。－－－－此时的图称为有向图。若Edge是对称的用无序对(x,y)表示x和y之间的一条边。－－－－此时的图称为无向图。不考虑顶点到自身的边：完全图：N个顶点，有N(N-1)/2条边的无向图；有向完全图：N个顶点，有N(N-1)条弧的有向图；稀疏图/稠密图网（Network）：带边权的图子图：无向图中两顶点互为邻接点；边和顶点相关联；顶点的度有向图中邻接到/邻接自顶点的入度/出度图中的顶点与边/弧之间有以下关系路径路径的长度回路/环简单路径简单回路/简单环连通连通图连通分量强连通图(有向图)强连通分
5、量连通图的生成树有向图的生成森林7.1.2图的基本运算及其ADT图的基本运算查找，插入和删除顶点在图中的位置：人为随意排列图的ADT声明ADTGraph{数据对象为D:D是具有相同特性的数据元素的集合,称为顶点集。数据间的关系R:R={Edge},Edge={
6、P(x,y)(x,yV),谓词P(x,y)定义了弧上的意义或信息}几种基本操作:graphCreate(&graph)graphDestroy(&graph)graphClear(&graph)创建空的图对象graph销毁一个已有的图graph将图graph清空graphEmpty(graph)gr
7、aphCount(graph)graphInsertVertex(&graph,dataIn)判图graph是否为空求图graph中顶点个数在图graph中插入新顶点,新顶点数据域的值是dataIngraphDeleteVertex(&graph,dltKey)graphInsertArc(&graph,fromKey,toKey)在图graph中插入新弧,弧头节点和弧尾节点关键字是fromKey和toKey在图graph中删除顶点,待删顶点数据域的关键字是dltKeygraphDeleteArc(&graph,fromKey,toKey)graphTraverse(graph,
8、visit)遍历图graph各顶点，并用visit代表的操作去处理各个顶点中的数据在图graph中删除弧,弧头节点和弧尾节点关键字是fromKey和toKeygraphRetrieveVertex(graph,key,&DataOut)}在图graph中寻找关键字为key的顶点,并将其信息放入DataOut输出参数中7.2图的存储结构图的常用存储结构数组表示法－－连续存储方式邻接表邻接多重表链式存储方式十字链表7.2.1数组表示法设G=(V,{E})是有N(N≥1)个顶点的图，则G的邻接矩阵是具有如下性质的N阶方阵：1若E或(vi,vj)EA[i,j]=0否则对
9、于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和。对于有向图，第i行的元素之和为顶点vi的出度OD(vi)，第j列的元素之和为顶点vj的入度ID(vj)。网的邻接矩阵可定义为：wij若E或(vi,vj)EA[i,j]=∞反之描述图时，我们同时使用两个数组：一维数组中存储的是各个顶点的信息；二维数组（邻接矩阵）中存储的是边或弧的信息。7.2.2邻接表在无向图的邻接表中，顶点vi的度恰为第i个链表中的节点数；而在有向图中，第i个链表中的节点数只是顶点vi的出度；为求入度，必须对整个邻接表扫描一遍。在所有链表中其邻接点域的值为i的节点的个数是顶点vi的入
10、度。有时，为了便于求每个顶点的入度，尚需建立一个有向图的逆邻接表，即对每个顶点vi建立以vi为弧头的链表。7.2.3邻接多重表邻接多重表适宜作无向图的存储结构。在无向图的邻接表表示法中，每条边(vi,vj)是用两个表节点表示的。这给某些图的操作带来不便。7.2.4十字链表十字链表：将有向图的邻接表和逆邻接表结合在一起得到的一种链表。图示参看图7.6在十字链表中既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度（若需要，可在建立十字链表的同时求出）。在
