计算机软件技术基础 第八章1VIP免费

图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径一、图的基本概念一、图的基本概念图定义图定义图是由顶点集合图是由顶点集合(vertex)及顶点间的关及顶点间的关系系集合组成的一种数据结构集合组成的一种数据结构：GraphGraph＝＝((VV,,EE))其中其中VV={={xx||xx某个数据对象某个数据对象}}是顶点的是顶点的有穷有穷非空集合；非空集合；EE={(={(xx,,yy)|)|xx,,yyVV}}是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)(edge)集集合。合。有向图与无向图有向图与无向图若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。完全图完全图对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1)，则称其为有向完全图。邻接顶点邻接顶点若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点vi和vj，或称（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的子图的子图。。路径路径在图G＝(V,E)中,若存在一个顶点序列vp1,vp2,…,vpm，使得(vi,vp1)、(vp1,vp2)、...、(vpm,vj)均属于E，则称顶点vi到vj存在一条路径。若一条路径上除了vi和vj可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。图的连通在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。权权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。12356874ABDCE1079667123151660304535804075生成树生成树一个连通图的生成树是它的极一个连通图的生成树是它的极小小连通子图，在连通子图，在nn个顶点的情形下，有个顶点的情形下，有nn--11条条边。边。不予讨论的图不予讨论的图包含顶点到其自身的边；包含顶点到其自身的边；一条边在图中重复出现一条边在图中重复出现二、图的存储结构二、图的存储结构在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个记录各个顶点信记录各个顶点信息息的的顶点表顶点表，还有一个，还有一个表示各个顶点之间关系表示各个顶点之间关系的的邻接矩阵邻接矩阵。。设图设图A=(A=(VV,,EE))是一个有是一个有nn个顶点的图，则图个顶点的图，则图的邻接矩阵是一个二维数组的邻接矩阵是一个二维数组AA.Edge.Edge[[nn][][nn]]，定，定义：义：无向图的邻接矩阵是对称的，有向图的邻接矩阵无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。可能是不对称的。邻接矩阵邻接矩阵(AdjacencyMatrix)(AdjacencyMatrix),),(,,]][[否则如果0><1A.EdgeEjiEjiji或者在有向图中在有向图中,,统计第统计第ii行行11的个数可得顶点的个数可得顶点ii的出度，的出度，统计第统计第jj列列11的个数可得顶点的个数可得顶点jj的入度。的入度。在无向图中在无向图中,,统计第统计第ii行行((列列)1)1的个数可得顶点的个数可得顶点ii的的度。度。网络的邻接矩阵网络的邻接矩阵),(,,,),,(]][[.jijiEjiEjijijiWjiEdge===!