数据结构课件chp6VIP免费

图的基本概念图的存储表示图的遍历与连通性最小生成树最短路径活动网络图的基本概念图的基本概念图定义图定义图是由顶点集合图是由顶点集合(vertex)及顶点间的及顶点间的关系集合组成的一种数据结构关系集合组成的一种数据结构：GraphGraph＝＝((VV,,EE))其中其中VV={={xx||xx某个数据对象某个数据对象}}是顶点的有穷非空集合；是顶点的有穷非空集合；EE={(={(xx,,yy)|)|xx,,yyVV}}或或EE={<={y>||xx,,yyVV&&&&PathPath((xx,,yy)})}是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)(edge)集合。集合。PathPath((xx,,yy))表示从表示从xx到到yy的一的一条单向通路条单向通路,,它是有方向的。它是有方向的。有向图与无向图有向图与无向图在有向图中，顶点对在有向图中，顶点对是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x,y)(x,y)是无序的。是无序的。完全图完全图若有若有nn个顶点的无向图有个顶点的无向图有nn((nn-1)/2-1)/2条边条边,,则此图为完全无向图。有则此图为完全无向图。有nn个顶点的有个顶点的有向图有向图有nn((n-n-1)1)条边条边,,则此图为完全有向图。则此图为完全有向图。邻接顶点邻接顶点如果如果((uu,,vv))是是EE(G)(G)中的一条边，中的一条边，则称则称uu与与vv互为邻接顶点互为邻接顶点。权权某些图的边具有与它相关的数某些图的边具有与它相关的数,,称之为权。这称之为权。这种带权图叫做网络。种带权图叫做网络。子图子图设有两个图设有两个图GG＝＝((VV,,EE))和和G‘G‘＝＝((VV’,’,EE‘)‘)。。若若VV’’VV且且EE‘‘EE,,则称图则称图G’G’是图是图GG的子的子图。图。顶点的度顶点的度一个顶点一个顶点vv的度是与它相关联的边的条的度是与它相关联的边的条数。记作数。记作TD(TD(vv))。。在有向图中在有向图中,,顶点的度等于该顶顶点的度等于该顶点的入度与出度之和。点的入度与出度之和。顶点顶点vv的入度的入度是以是以vv为终点的有向边的条数为终点的有向边的条数,,记作记作ID(ID(vv));;顶点顶点vv的出度的出度是以是以vv为始点的有为始点的有向边的条数向边的条数,,记作记作OD(OD(vv))。。路径路径在图在图GG＝＝((VV,,EE))中中,,若从顶点若从顶点vvii出出发发,,沿一些边经过一些顶点沿一些边经过一些顶点vvpp11,,vvpp22,…,,…,vvpmpm，到达，到达顶点顶点vvjj。则称顶点序列。则称顶点序列((vviivvpp11vvpp22......vvpmpmvvjj))为从顶为从顶点点vvii到顶点到顶点vvjj的路径的路径。它经过的边。它经过的边((vvii,,vvpp11))、、((vvpp11,,vvpp22))、、......、、((vvpmpm,,vvjj))应是属于应是属于EE的边。的边。路径长度路径长度非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。简单路径简单路径若路径上各顶点若路径上各顶点vv11,,vv22,...,,...,vvmm均不互相均不互相重复重复,,则称这样的路径为简单路径。则称这样的路径为简单路径。回路回路若路径上第一个顶点若路径上第一个顶点vv11与最后一个顶点与最后一个顶点vvmm重合重合,,则称这样的路径为回路或环。则称这样的路径为回路或环。连通图与连通分量连通图与连通分量在无向图中在无向图中,,若从顶点若从顶点vv11到到顶点顶点vv22有路径有路径,,则称顶点则称顶点vv11与与vv22是连通的。如果是连通的。如果图中任意一对顶点都是连通的图中任意一对顶点都是连通的,,则称此图是连通图。则称此图是连通图。非连通图的极大连通子图叫做连通分量。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量强连通图与强连通分量在有向图中在有向图中,,若对若对于每一对顶点于每一对顶点vvii和和vvjj,,都存在一条从都存在一条从vvii到到vvjj和从和从vvjj到到vvii的路径的路径,,则称此图是强连通图。非强连则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。通图的极大强连通子图叫做强连通分量。生成树生成树一个连通图的生成树...