数据结构08VIP免费

图的基本概念图的存储表示图的遍历与连通性最小生成树最短路径活动网络图的基本概念图的基本概念图定义图定义图是由顶点集合图是由顶点集合(vertex)及顶点间及顶点间的关系集合组成的一种数据结构的关系集合组成的一种数据结构：GraphGraph＝＝((VV,,EE))其中其中VV={={xx||xx某个数据对象某个数据对象}}是顶点的有穷非空集合；是顶点的有穷非空集合；EE={(={(xx,,yy)|)|xx,,yyVV}}或或EE={<={y>||xx,,yyVV&&&&PathPath((xx,,yy)})}是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(ed(edge)ge)集合。集合。PathPath((xx,,yy))表示从表示从xx到到yy的一条的一条单向通路单向通路,,它是有方向的。它是有方向的。有向图与无向图有向图与无向图在有向图中，顶点对在有向图中，顶点对是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x,(x,y)y)是无序的。是无序的。完全图完全图若有若有nn个顶点的无向图有个顶点的无向图有nn((nn-1)/2-1)/2条边条边,,则此图为完全无向图。有则此图为完全无向图。有nn个顶点的有向图有个顶点的有向图有nn((n-n-1)1)条边条边,,则此图则此图为完全有向图。为完全有向图。00001111222265433邻接顶点邻接顶点如果如果((uu,,vv))是是EE(G)(G)中的一中的一条边，则称条边，则称uu与与vv互为邻接顶点互为邻接顶点。子图子图设有两个图设有两个图GG＝＝((VV,,EE))和和G‘G‘＝＝((VV’,’,EE‘)‘)。若。若VV’’VV且且EE‘‘EE,,则称图则称图G’G’是图是图GG的子图。的子图。权权某些图的边具有与它相关的数某些图的边具有与它相关的数,,称之称之为权。这种带权图叫做网络。为权。这种带权图叫做网络。0123子图0130123023顶点的度顶点的度一个顶点一个顶点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重合重合,,则称这样的路径为回路或环。则称这样的路径为回路或环。012301230123连通图与连通分量连通图与连通分量在无向图中在无向图中,,若从顶若从顶点点vv11到顶点到顶点vv22有路径有路径,,则称顶点则称顶点vv11与与vv22是是连通的。如果图中任意一对顶点都是连通的连通的。如果图中任意一对顶点都是连通的,,则称此图是连通图。非连通图的极大连通则称此图是连通图。非连通图的极大连通子图叫做连通分量。子图叫做连通分量。强连通图与强连通分量强连通图与强连通分量在有向图中在有向图中,,若若对于每一对顶点对于每一对顶点vvii和和vvjj,,都存在一条从都存在一条从vvii到到vvjj和从和从vvjj到到vvii的路径的路径,,则称此图是强连通图。则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分非强连通图的极大强连通子图叫做强连...