电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

lecture graphVIP免费

lecture graph_第1页
1/95
lecture graph_第2页
2/95
lecture graph_第3页
3/95
1清华大学数据结构教研组GRAPH(图)Lecture-1005/092�图的基本概念�图的存储表示�图的遍历与连通性�最小生成树�最短路径�活动网络图3�图定义图是由顶点集合(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的一条单向通路,它是有方向的。图的基本概念4�有向图与无向图在有向图中,顶点对是有序的。在无向图中,顶点对(x,y)是无序的。�完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图。有n个顶点的有向图有n(n-1)条边,则此图为完全有向图。000011112222654335�邻接顶点如果(u,v)是E(G)中的一条边,则称u与v互为邻接顶点。�子图设有两个图G=(V,E)和G'=(V',E')。若V'⊆V且E'⊆E,则称图G'是图G的子图。�权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。子图012301301230236�顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。�顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。�路径在图G=(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm,到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。7�路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。�简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。�回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。0123012301238�连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。�强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。�生成树一个连通图的生成树是其极小连通子图,在n个顶点的情形下,有n-1条边。9�图的模板基类在模板类定义中的数据类型参数表中,T是顶点数据的类型,E是边上所附数据的类型。�这个模板基类是按照最复杂的情况(即带权无向图)来定义的,如果需要使用非带权图,可将数据类型参数表改为。�如果使用的是有向图,也可以对程序做相应的改动。图的存储表示10constintmaxWeight=……;//无穷大的值(=∞)constintDefaultVertices=30;//最大顶点数(=n)templateclassGraph{//图的类定义protected:intmaxVertices;//图中最大顶点数intnumEdges;//当前边数intnumVertices;//当前顶点数intgetVertexPos(Tvertex);//给出顶点vertex在图中位置public:图的模板基类11Graph(intsz=DefaultVertices);//构造函数~Graph();//析构函数boolGraphEmpty()const//判图空否{returnnumEdges==0;}intNumberOfVertices(){returnnumVertices;}//返回当前顶点数intNumberOfEdges(){returnnumEdges;}//返回当前边数virtualTgetValue(inti);//取顶点i的值virtualEgetWeight(intv1,intv2);//取边上权值virtualintgetFirstNeighbor(intv);//取顶点v的第一个邻接顶点12virtualintgetNextNeighbor(intv,intw);//取邻接顶点w的下一邻接顶点virtualboolinsertVertex(constTvertex);//插入一个顶点vertexvirtualboolinsertEdge(intv1,intv2,Ecost);//插入边(v1,v2),权为costvirtualboolremoveVertex(intv);//删去顶点v和所有与之相关联的边virtualboolremoveEdge(intv1,intv2);//在图中删去边(v1,v2)};13�在图的邻接矩阵表示中,有一个记录各个顶点信息的顶点表,还有一个表示各个顶点之间关系的邻接矩阵。�设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n],定义:⎩⎨⎧∈∈=,),(,,]][[...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部