资源描述：
《lecture graph》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1GRAPH（图）Lecture-1005/09清华大学数据结构教研组图2£图的基本概念£图的存储表示£图的遍历与连通性£最小生成树£最短路径£活动网络图的基本概念3£图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x
2、x∈某个数据对象}是顶点的有穷非空集合；E={(x,y)
3、x,y∈V}//无向或E={
4、x,y∈V&&Path(x,y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条单向通路,它是有方向的。£有向图与无向图在有向图中，顶点对是有序的。在无向图
5、中，顶点对(x,y)是无序的。£完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图。有n个顶点的有向图有n(n-1)条边,则此图为完全有向图。000011212133456224£邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。£子图设有两个图G＝(V,E)和G'＝(V',E')。若V'⊆V且E'⊆E,则称图G'是图G的子图。0000子图1211223333£权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。5£顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。£顶点v的
6、入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。£路径在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点v,v,…,v，到达顶p1p2pm点v。则称顶点序列(vvv...vv)为从顶jip1p2pmj点v到顶点v的路径。它经过的边(v,v)、ijip1(v,v)、...、(v,v)应是属于E的边。p1p2pmj6£路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。£简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。£回路若路径上第一个顶点v
7、1与最后一个顶点v重合,则称这样的路径为回路或环。m0001212123337£连通图与连通分量在无向图中,若从顶点v1到顶点v有路径,则称顶点v与v是连通的。如212果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。£强连通图与强连通分量在有向图中,若对于每一对顶点v和v,都存在一条从v到v和从v到ijijjv的路径,则称此图是强连通图。非强连通图i的极大强连通子图叫做强连通分量。£生成树一个连通图的生成树是其极小连通子图，在n个顶点的情形下，有n-1条边。8图的存储表示9£图的模板基类在模板类定义中的数据类型参数表8、E>中，T是顶点数据的类型，E是边上所附数据的类型。£这个模板基类是按照最复杂的情况（即带权无向图）来定义的，如果需要使用非带权图，可将数据类型参数表改为。£如果使用的是有向图，也可以对程序做相应的改动。图的模板基类10constintmaxWeight=……;//无穷大的值(=∞)constintDefaultVertices=30;//最大顶点数(=n)templateclassGraph{//图的类定义protected:intmaxVertices;//图中最大顶点数intnumEdges;//
9、当前边数intnumVertices;//当前顶点数intgetVertexPos(Tvertex);//给出顶点vertex在图中位置public:Graph(intsz=DefaultVertices);//构造函数～Graph();//析构函数boolGraphEmpty()const//判图空否{returnnumEdges==0;}intNumberOfVertices(){returnnumVertices;}//返回当前顶点数intNumberOfEdges(){returnnumEdges;}//返回当前边数virtualTgetValue(inti);//取顶
10、点i的值virtualEgetWeight(intv1,intv2);//取边上权值virtualintgetFirstNeighbor(intv);//取顶点v的第一个邻接顶点11virtualintgetNextNeighbor(intv,intw);//取邻接顶点w的下一邻接顶点virtualboolinsertVertex(constTvertex);//插入一个顶点vertexvirtualboolinsertEdge(intv1,intv2,Ecost);//插入边(v1,v2)
