数据结构第7章VIP免费

图的基本概念图的基本概念图的存储结构图的存储结构图的遍历图的遍历最小生成树最小生成树7.17.1图的基本概念图的基本概念图定义图定义图是由顶点集合图是由顶点集合(vertex)及顶点间的关系及顶点间的关系边（或者弧边（或者弧))集合组成的一种数据结构集合组成的一种数据结构：GraphGraph＝＝((VV,,EE))其中其中VV={={xx||xx某个数据对象某个数据对象}}是顶点的有是顶点的有穷穷非空集合；非空集合；EE={={或或(v,w)|(v,w)|vv,,wwVV}}是顶点之间关系的有穷集合，谓词是顶点之间关系的有穷集合，谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息,,谓词是用来刻划个体词的性质谓词是用来刻划个体词的性质或事物之间关系的词或事物之间关系的词..有向图与无向图有向图与无向图若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向((xx,,yy))的，则称G为无向图.((xx,,yy))称为边。称为边。V1V1V3V3V4V4V5V5V2V2V4V4V3V3V2V2V1V1无向图无向图G1G1有向图有向图G2G2G2=(V2,E2)G2=(V2,E2)V2={v1,v2,v3,v4}V2={v1,v2,v3,v4}E2={,,,}E2={,,,}G1=G1=((VV,,EE))集合集合VV＝＝{v1,v2,v3,v4,v5}{v1,v2,v3,v4,v5}集合集合EE＝＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。。2002-11-12mmmm4权权某些图的边具有与它相关的数,称之为权。在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。带权图叫做网。有向网、无向网。12356874ABDCE10796671231516603045358040752002-11-12mmmm6完全图完全图对有n个顶点的图，若为有向图且边数为n(n-1)，则称其为有向完全图。若为无向图且边数为n(n-1)/2，则称其为无向完全图；边或弧数,称vi邻接到vj，弧关联于顶点vi和vj.顶点的度顶点的度一个顶点一个顶点vv的度是与它相关联的边的条的度是与它相关联的边的条数。数。记作记作TD(TD(vv))。。顶点顶点vv的入度的入度是以是以vv为终点的有向边的条数为终点的有向边的条数,,记作记作ID(ID(vv));;顶点顶点vv的出度的出度是以是以vv为始点的有向边的条为始点的有向边的条数数,,记作记作OD(OD(vv))。。子图子图设有两个图设有两个图GG＝＝((VV,,EE))和和G‘G‘＝＝((VV’,’,EE‘)‘)。。若若VV’’VV且且EE‘‘EE,,则称图则称图G’G’是图是图GG的子图的子图。。5路径路径在图G＝(V,E)中,若存在一个顶点序列vp1,vp2,…,vpm，使得(vi,vp1)、(vp1,vp2)、...、(vpm,vj)均属于E，则称顶点vi到vj存在一条路径。若一条路径上除了vi和vj可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为回路或环,其余顶点均不相同，称为简单回路6图的连通在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。BBEEAADDCCFFBBAAFFEEDDCC2002-11-12mmmm10强连通图与强连通分量强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。V2V2V4V4V3V3V1V1V4V4V3V3V2V2V1V1生成树生成树一个连通图的生成树是它的极一个连通图的生成树是它的极小小连通子图，含图中连通子图，含图中nn个顶点，有个顶点，有nn-1-1条条边。边。V1V1V3V3V4V4V5V5V2V2V1V1V3V3V4V4V5V5V2V2含图中含图...