数据结构第7章

《数据结构第7章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图图的基本概念图的存储结构图的遍历最小生成树2002-11-121mmmm7.1图的基本概念图定义图是由顶点集合(vertex)及顶点间的关系边（或者弧)集合组成的一种数据结构：Graph＝(V,E)其中V={x

2、x某个数据对象}是顶点的有穷非空集合；E={或(v,w)

3、v,wV}是顶点之间关系的有穷集合，谓词P(v,w)定义了弧的意义或信息,谓词是用来刻划个体词的性质或事物之间关系的词.2002-11-122mmmm有向图与无向图若图G中的每条边都是有方向的，则称G为有向图。有向边

4、也称为弧。若图G中的每条边都是没有方向(x,y)的，则称G为无向图.(x,y)称为边。V1V3V4V5V2V4V3V2V1无向图G1有向图G2G2=(V2,E2)V2={v1,v2,v3,v4}E2={,,,}G1=(V,E)集合V＝{v1,v2,v3,v4,v5}集合E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。2002-11-123mmmm权某些图的边具有与它相关的数,称之为权。在实际应用中，权值可以有某种

5、含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。带权图叫做网。有向网、无向网。2002-11-124mmmm12356874ABDCE10796671231516603045358040752002-11-125mmmm完全图对有n个顶点的图，若为有向图且边数为n(n-1)，则称其为有向完全图。若为无向图且边数为n(n-1)/2，则

6、称其为无向完全图；边或弧数,称vi邻接到vj，弧关联于顶点vi和vj.2002-11-126mmmm顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(

7、v)。子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。52002-11-127mmmm路径在图G＝(V,E)中,若存在一个顶点序列vp1,vp2,…,vpm，使得(vi,vp1)、(vp1,vp2)、...、(vpm,vj)均属于E，则称顶点vi到vj存在一条路径。若一条路径上除了vi和vj可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为回路或环,其余顶点均不相同，称为简单回路62002-11-128mmmm图的连通在无向图G中，若两个顶点v

8、i和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。BEADCFBAFEDC2002-11-129mmmm强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。V2V4V3V1V4V3V2V12002-11-1210mmmm生成树一个连通图的生成树是它的极小连通子图，含图中n个顶点，有n-1条边。V1V3V4V5V2V1V3V4V5V2

9、含图中n个顶点，有n-1条边的图一定生成树吗？2002-11-1211mmmm生成森林在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。BEADCFBAFEDC2002-11-1212mmmm基本操作P：结构的建立和销毁:CreateGraph(&G,V,VR);//按V和VR的定义构造图G。DestroyGraph(&G);//销毁图G。对顶点的访问操作:LocateVex(G,u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。Ge

10、tVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。2002-11-1213mmmm对邻接点的操作:FirstAdjVex(G,v);//返回v的第一个邻接点。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对