数据结构图的基本概念本

1、第七章 图图与其它结构对比图是一种比线性表和树更为复杂的数据结构。图是一种比线性表和树更为复杂的数据结构。线性表中，数据元素之间仅有线性关系，每个数据元线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。素只有一个直接前驱和一个直接后继。树形结构中，数据元素之间有着明显的层次关系，并且树形结构中，数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层中的多个元素有关，但每一层的数据元素可能和下一层中的多个元素有关，但只能和上一层中一个元素有关。只能和上一层中一个元素有关。图形结构中，结点之间的关系是任意的，图中任意两个数据元素之间都可能相关。本章内容1.图

2、的基本概念图的基本概念2.图的存储结构图的存储结构3.图的遍历图的遍历4.图的连通性和最小生成树问题图的连通性和最小生成树问题5.图的拓扑排序和关键路径图的拓扑排序和关键路径6.图的最短路径图的最短路径图的结构定义图图G是由两个集合是由两个集合V和和R组成。其中组成。其中V是顶是顶点点的有穷非空集合，的有穷非空集合，R是是V中中顶点偶对顶点偶对的的有穷集合。有穷集合。Graph = (V , R )V=图中所有顶点图中所有顶点R=图中各个顶点之间的关系图中各个顶点之间的关系VR其中，VR | v,wV 且 P(v,w) 表示从 v 到 w 的一条弧弧，并称 v 为弧尾弧尾，w 为弧头弧头。 谓

3、词 P(v,w) 定义了弧 的意义或信息。 由于由于“弧弧”是有方向的，因此称由是有方向的，因此称由顶点集顶点集和和弧集弧集构成的图为构成的图为有向图有向图。EACBD例如例如:G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 若若 VR 必有必有 VR, 则称则称 (v,w) 为顶点为顶点v 和顶点和顶点 w 之间存在一条之间存在一条边边。 B CA D F E由顶点集顶点集和边边集集构成的图称作无向图无向图。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A,B), (A,E), (B,E), (C,D), (D,

4、F), (B,F), (C,F) 图的基本术语图的基本术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABECFAEFBC设图G=(V,VR) 和图 G=(V,VR),且 VV, VRVR,则称 G 为 G 的子图子图。1597211132弧或边带权弧或边带权的图分别称作有向网有向网或无无向网向网。假设图中有 n 个顶点，e 条边，则： 含有 e=n(n-1)/2 条边边的无向图称作无向完无向完全图；全图； 含有 e=n(n-1) 条弧弧的有向图称作有向完有向完全图全图； 若边或弧的个数 enlo

5、gn，则称作稀疏稀疏图图，否则称作稠密图稠密图。对于无向图无向图G，顶点v 和顶点w 之间存在一条边边，则称顶点v 和w 互为邻接点邻接点，ACDFE例如例如:TD(B) = 3TD(A) = 2 边(v,w) 和顶点v 和w相关联关联。 和顶点v 关联的边的数目关联的边的数目定义为顶点的度顶点的度。B顶点的出度出度: 以顶点v为为弧尾弧尾的弧的数目；ABECF对有向图有向图来说，顶点的入度入度: 以顶点v为弧头为弧头的弧的数目。顶点的度顶点的度(TD)=出度出度(OD)+入度入度(ID)例如例如:ID(B) = 2OD(B) = 1TD(B) = 3一般地，如果顶点vi的度记为TD(vi)，

6、那么一个有n个顶点，e条边或弧的图，满足如下关系：11( )2niieTD v设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECF如如:长度为3的路径A,B,C,F简单路径简单路径:序列中顶点不重复出现的路径。回路或环回路或环:序列中第一个顶点和最后一个顶点相同的路径。简单回路或简单环简单回路或简单环：除第一个和最后一个顶点外，其余顶点不出现重复的回路。若无向图无向图G中任意两个顶点之间都有路径都有路径相通相通，则称此图为连连通图通

7、图；若无向图为非连通图非连通图，则图中各个极大连通极大连通子图子图称作此图的连通连通分量分量。BACDFEBACDFE 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECFABECF对对有向图有向图，否则，其各个极大极大强连通子图称作它的强强连通分量连通分量。假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通极小连通子图子图，称该极小连通子图极小连通子图为此连通图的生生成树成树。对非连通图非连通图，则称由各个连通分各个连通分量的生成树量的生成树的集合为此非连通图的生成森林生成森林。BACDFE图的基本操作1.图的建立和销毁图的建立和销毁CreatGraph(&G, V, VR)DestroyGraph(&G)2.图的遍历图的遍历DFSTraverse(G, v)深度优先遍历图深度优先遍历图GBFSTraverse(G, v)广度优先遍历图广度优先遍历图G3.对顶点的操作对顶点的操作LocateVex(G, u)GetVex(G, v)PutVex(&G, v, value)InsertVex(&G, v)DeleteVex(&