图型结构.docVIP

第六讲　图型结构 一、图的概念 图（graph）是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都着广泛的应用。图的二元组定义为： G = （V , E） 　　其中V是非空的顶点集合，即 V = {vi | 1 = i = n, n = 1 , vi ∈elemtype，n 为顶点数} E是V上顶点的序偶或无序对的集合，即对应边的集合。 二、图的基本术语 图1　　有向图　　　　　　　　　　图2　　无向图 1、 端点和邻接点 在一个无向图中，若存在—条边（vi，vj），则称vi,vj为此边的两个端点，并称它们互为邻接点（adjacent），即vi是vj的一个邻接点，vj也是vi的一个邻接点。 在一个有向图中，若存在一条边vi, vj，则称此边是顶点vi的一条出边（outedge），顶点vj的一条入边（inedge）； 称Vi为此边的起始端点，简称起点或始点，vj为此边的终止端点，简称终点；称vi和vj互为邻接点，并称vj是vi的出边邻接点，vi是vj的入边邻接点。 2、 顶点的度、入度、出度 无向图顶点v的度（degree）定义为以该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为D（v）。如图2中v1顶点的度为2，v2顶点的度为3。有向图中顶点v的度有入度和出度之分，入度（indegree）是该顶点的入边的数目，记为ID（v）；出度（outdegree）是该顶点的出边的数目，记为OD（v）顶点v的度等于它的入度和出度之和，即D（v）=ID（v）+OD（v）。 3、 完全图、稠密图、稀疏图 若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。显然，若完全图是无向的，则图中包含有n（n-1）/2条边, 若完全图是有向的，则图中包含有n（n-1）条边。当一个图接近完全图时，则可称为稠密图，相反地，当一个图有较少的边数（即e n（n – 1））时，则可称为稀疏图。 4、 子图 设有两个图G = （V, E）和G’ ＝ （V’, E’）, 若V’是V的子集，且E’是E的子集，则成G’是G的子图。 图 子图 5、 路径和回路 在一个图G中，从顶点v到顶点v’的一条路径（path）是一个顶点序列vi0, vi1, vi2, vim,其中v = vi0, v’ = vim, 若此图是无向图，则（vi,j-1, vij） ∈E（G），（1≤j≤m）；若此图是有向图，则vi,j-1, vij∈E（G），（1≤j≤m）。路径长度是指该路径上经过的边的数目。若一条路径上除了前后端点可以相同外，所有顶点均不同，则称此路径为简单路径。若一条路径上的前后两端点相同，则被称为回路或环（cycle），前后两端点相同的简单路径被称为简单回路或简单环。 6、 连通和连通分量 在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。 7、 强连通图和强连通分量 在有向图G中，若从顶点vi到顶点vj有路径，则称从vi到vj是连通的。若图G中的任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。 8、 权和网 在一个图中．每条边可以标上具有某种含义的数值，此数值称为该边的权（weight）。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长度或等级；对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压；对于一个反映零件装配的图，边上的权可表示一个端点需要装配另一个端点的零件的数量；对于一个反映工程进度的图，边上的权可表示从前一子工程到后一子工程所需要的天数。边上带有权的图称作带权图，也常称作网（network）。 三、图的存储结构 1、 邻接矩阵 邻接矩阵（adjacency matrix）是表示顶点之间相邻关系的矩阵。设G＝（V，E）是具有n个顶点的图，顶点序号依次为1、2、···、n，则G的邻接矩阵是具有如下定义的n阶方阵。 有向图 无向图 2、 邻接表 邻接表（adjacency list）是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。为顶