文档介绍：第 10 章图图(graph) 是一种比线性表、树更为复杂的数据结构。在线性表中,数据元素之间呈线性关系,即每个元素只有一个直接前驱和一个直接后继。图的应用领域十分广泛,如化学分析、工程设计、遗传学、人工智能等。本章主要介绍图的定义、图的存储结构、图的遍历、最小生成树、关键路径和最短路径。本章重点: 1、图的定义及性质 2、图的邻接矩阵和邻接表表示 3、图的各种遍历 4、最小生成树 5、关键路径 6、最短路径 图的定义与相关概念图G也是由数据元素集合 V与边的集合 E构成的。在图中,数据元素通常称为顶点( Vertex )。其中,顶点集合 V不能为空,边表示顶点之间的关系。若< x,y >∈E,则< x,y >表示从顶点 x到顶点 y存在一条弧( Arc ), x称为弧尾( tail )或起始点( initial node ), y称为弧头( head )或终端点( terminal node )。这样的图被称为有向图( digraph )。如果< x,y >∈E且有< y,x >∈E,即 E是对称的,则用无序对( x,y ) 代替有序对< x,y >和< y,x >,表示 x与y之间存在一条边( edge ), 这样的图称为无向图( undigraph )。如图 所示。 图的定义与相关概念图G的形式化定义为: G=(V,E) ,其中, V={ x|x ∈数据元素集合}, E={< x,y >| Path(x,y)/\(x ∈ V,y ∈V )} 。 Path(x,y )表示< x,y >的意义或信息。在图 中,有向图 G 1可以表示为 G 1 =(V1,E1) ,其中,顶点的集合为 V 1 ={ a,b,c,d },边的集合为 E 1 ={< a,b >,< a,d >,< b,c >,< c,a >,< c,b >,< d,c >} 。无向图 G 2可以表示为 G 2 =(V 2 ,E 2),其中,顶点的集合为 V 2 ={ a,b,c,d },边的集合为 E 2 ={( a,b),(a,c),(a,d),(b,c),(c,d )} 。 图的定义与相关概念 G=(V,E) ,若边(v i ,v j)∈E,则称 v i和v j互为邻接点( adjacent ),即 vi和 vj相邻接。边(v i ,v j)依附于顶点 v i和 vj,或者说( vi,vj )与顶点 v i、 vj相关联。对于有向图 G=(V,A) ,若弧< vi,vj >∈A,则称顶点 vi邻接到顶点 vj,顶点 vj邻接自顶点 vi。弧< vi,vj >和顶点 vi、 vj相关联。无向图 G 2的边的集合为 E={( a,b),(a,c),(a,d),(b,c),(c,d )} , 顶点 a和b互为邻接点,边( a,b )依附于顶点 a和b。顶点 c和d互为邻接点,边( c,d )依附于顶点 c和d。有向图 G1 的弧的集合为 A={< a,b >,< a,d >,< b,c >,< c,a >,< c,b >,< d,c >} ,顶点 a邻接到顶点 b,弧< a,b >与顶点 a和b相关联。顶点 c邻接自顶点 d,弧< d,c >与顶点 d和c相关联。 图的定义与相关概念 ,顶点 v的度是指与 v相关联的边的数目,记作 TD(v )。对于有向图,以顶点 v为弧头的数目称为顶点 v的入度( indegree ),记作 ID(v )。以顶点 v为弧尾的数目称为 v的出度( outdegree ),记作 OD(v )。顶点 v的度(degree) 为 TD(v )= ID(v)+OD(v )。无向图 G 2中顶点 a的度为 3,顶点 b的度为 2,顶点 c的度为 3,顶点 d的度为2。有向图 G 1的弧的集合为 A={< a,b >,< a,d >,< b,c >,< c,a >,< c,b >,< d,c >} ,顶点 a、b、c 和d的入度分别为 1、2、2和1,顶点 a、b、c和d的出度分别为 2、1、 2和1,顶点 a、b、c和d的度分别为 3、3、4和2。若图的顶点的个数为 n,边数或弧数为 e,顶点 vi的度记作 TD(vi ),则顶点的度与弧或者边数满足关系: e= 图的定义与相关概念 G中,从顶点 v到顶点 v’的路径( path )是从 v出发,经过一系列的顶点序列到达顶点 v’。如果 G是有向图,则路径也是有向的,路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环( cycle )。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外,其他顶点不重