资源描述：
《数据结构-图及其存储结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图及其存储结构1.图的有关概念①图(Graph)的ADT定义：图是n(n≥0)个结点的有限集合。在任意一个图中任意两个结点之间都可能相关。图的ADT定义如下：一、基本概念数据对象V：V是具有相同特性的数据元素的集合，并称为顶点集合。数据关系R：R={E}E={
2、v,w∈V,且有谓词P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧上的信息或权值}基本操作P：详见P.156。图的二元组表示：G=(V，E)E即为图中边或弧的集合。1.图的有关概念②图的有关术语：一、基本概念图中的数据元素称为顶点；有向图；弧；弧头；弧尾；无向图；边；
3、*定理：若用e表示有向图或无向图中弧或边的条数，即e=
4、E
5、,则有：在有向图中：0≤e≤n(n-1)在无向图中：0≤e≤n(n-1)/2具有n(n-1)/2条边的无向图称为完全图：具有n(n-1)条边的有向图称为有向完全图：v1v2v3v401231.图的有关概念②图的有关术语：一、基本概念顶点的度；有向图中顶点的度是该顶点的入度与出度之和。无向图中顶点的度是与该顶点相关联的边的条数。子图：对于G1=(V1,E1),G2=(V2,E2),若V2V1，E2E1，则称G2是G1的子图。回路（环）：若一条路径上的顶点均不相同则该路径称为简单路径；除了顶点和终点相同外，路
6、径上的其他顶点均不相同的路径称为回路或环。v1v2v3v401231.图的有关概念②图的有关术语：一、基本概念无向图中任意两个顶点都是连通的，则该图为连通图。有向图中任何有序顶点对之间都有有向路径，则称该图是强连通的。无向图中最大的连通子图称为该图的连通分支；有向图中相应地称为强连通分支。v1v2v3v401231.图的有关概念②图的有关术语：一、基本概念一个连通无向图的生成树是该图的一个连通分量，它包含有该图的所有n个顶点以及连接这n个顶点的（n-1）条边。边或弧上带权值的图称为带权图或网（分为无向网和有向网）。一个无向图的所有生成树中，边上的权值之和最小的生成
7、树称为该图的最小生成树或最小代价生成树。v1v2v3v4v5v665512564631.图的有关概念②图的有关术语：一、基本概念图中顶点的“序号”及其邻接点的“序号”：由于图中顶点之间不存在全序关系，所以无法将图中顶点进行线性排序。但为了实现图的存储结构，我们必须给每个顶点附加一个人为规定的“序号”。这个序号即称为该顶点在图中的位置。对于任意一个顶点而言，若它有两个以上的邻接点，则它的邻接点也有所谓“第一个邻接点”，“第二个邻接点”，......，这个顺序也称为邻接顺序。2.图的遍历一、基本概念图的遍历：从图中某一顶点出发按一定规律沿着图中的边或弧访问每一顶点一次
8、且仅一次的操作称为对图的遍历。*图的遍历有两种方法：深度优先遍历和广度优先遍历*若图是连通的或是强连通的，则遍历过程所经过的边（或弧）加上图中所有顶点就是图的一棵生成树。*对于不连通图而言，从某一连通分支中的某一顶点出发执行一次“遍历”算法可得该连通分支的生成子树。若干次使用上述方法可得图的生成森林。1.图的数组表示法二、存储结构*思想：用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系：即用一个一维数组vexs存放各顶点的有关信息；用一个二维数组arcs存放各条边或弧的有关信息（如存放边或弧上的权值）。1.图的数组表示法二、存储结构#defineINF
9、INITYINT_MAX//用以表示∞#defineMAX_VERTEX_NUM20//最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//有向图,有向网,无向图,无向网typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型，对无权图，用0或1表示//相邻否；对带权图，则为权值类型（如整型）InfoType*info;//该弧相关信息存放位置指针}ArcCell,AdiMatrix[MAX_VERTEX_NUM,MAX_VERTEX_NUM];//AdiMatrix为一个数组元素类型为ArcC
10、ell的二维数组typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//一维数组存放顶点的信息AdjMatrixarcs;//二维数组存放边或弧上的信息（如权值）intvexnum,arcnum;//分别存放图的顶点数目和弧的条数GraphKindkind;//图的种类标志}MGraph1.图的数组表示法二、存储结构例1：例如：MGraphG1;0110000000011000G1.vexs[0]=v1，......，G1.vexs[3]=v4；G1.vexnum=4；G1.arcnum=4；G1.kind=DGG1.arcs
11、=v1v2
