图形结构.ppt

1.4 图形结构 ◆图是一种比线性表和树更为复杂的数据结构。在图中，元素间的关系是多对多的，即任何两个元素都有可能存在关系。 ◆图的应用非常广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中(日常生活中的交通图等)。 ◆在离散数学中，图论是专门研究图的性质的数学分支。 ◆在数据结构中对图的讨论主要侧重于图在计算机中的存储方式和有关操作的算法。 1.4.1 图的定义和术语 图的定义： 图是一种数据元素之间多对多的数据结构，可以定义为一个二元组：G=(V,VR)。 图中的数据元素称为顶点(vertex),V是顶点的有穷非空集合；VR是V上顶点的序偶或无序对的集合。 若v,w ? VR，则v,w 表示从v到w的一条弧(Arc),且称v为弧尾(Tail)或初始点(Initial node),称w为弧头(Head)或终端点(Terminal node),此时的图称为有向图(Digraph)。 若v,w ? VR必有w, v ? VR，即VR是对称的，则以无序对(v,w)代替两个有序对，表示 v和w之间的一条边(Edge),此时的图称为无向图(Undigraph)。可以说图由非空顶点集和边集所组成。 图的示例 无向图G1 有向图G2 图的基本术语 完全图、稠密图、稀疏图 约定：用n表示图中顶点的数目，用e表示边或弧的数目 若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。 当一个图接近完全图时，称为稠密图。 当一个图含有较少的边或弧(enlogn)时，称为稀疏图。 图的基本术语(2) 权和网：在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边的权。边上带有权的图称为网。 子图：设有两个图G=(V,{E})和G’=(V’,{E’}),如果V’? V，E’ ? E，则称G’ 是G的子图。例子见P60 端点和邻接点：在一个无向图中，若(v,v’)?E,则称v,v’为此边的两个端点， v,v’互为邻接点。 顶点的度、入度、出度：无向图中顶点v的度定义为和v相关联的边的数目，记为TD(v)。有向图中，顶点v的入度是该顶点入边的数目，记为ID(v)，出度是该顶点出边的数目，记为OD(v)。显然TD(v)= ID(v) + OD(v)。一般地，e=?TD(vi)/2 。 图的基本术语(3) 路径和回路：在一个图中，从顶点v到顶点v’的一条路径是一个顶点序列。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。 连通图和连通分量：在无向图G中，若两个顶点v和v’之间有路径存在，则称v 和v’ 是连通的。若G中任意两个顶点都是连通的，则称G为连通图，否则称为非连通图。非连通图的极大连通子图叫做连通分量。例子见P61。 图的基本术语(4) 强连通图与强连通分量：在有向图中, 若对于每一对顶点v和v’, 都存在一条从v到v’和从v’到v的路径, 则称此图是强连通图。有向图中极大强连通子图叫做强连通分量。例子见P61 。 生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。 1.4.1图的存储结构 图的存储结构又称图的存储表示或图的表示。它有多种方法，主要介绍邻接矩阵、邻接表。 邻接矩阵：表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。 邻接矩阵是一个(n×n)阶方阵，n为图的顶点数，它的每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。规定矩阵的元素为： 无向图的邻接矩阵 有向图的邻接矩阵 无向图的邻接矩阵是对称的，如果A[i,j]=1，必有A[j,i]=1。这说明，只输入和存储其上三角阵元素即可得到整个邻接矩阵。 一般有向图的邻接矩阵是不对称的，A[i,j]不一定等于A[j,i]。 邻接矩阵用二维数组即可存储，定义如下： int adjmatrix = ARRAY[n][n]; 如果图的各边是带权的，只需将矩阵中的各个1元素换成相应边的权即可。 邻接矩阵的若干说明 邻 接 表 邻接表是图的一种链式存储结构。 在邻接表结构中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边，即对于无向图每个结点