第七章 图前面介绍了两种基本数据结构：线性表和树。线性表是一种线性结构，除了头尾结点外，每个结点只有一 个前驱结点和一个后继结点。树是一种非线性结构，数据元素(结点)之间的关系是父子关 系，每个结点有且仅有一个双亲结点，有0个或多个孩子结 点，在结点之间建立了一种层次关系。图是一种新的数据结构，其数据元素(顶点)之间的关系是任 意的，每个顶点都可以和其他任何顶点相关。是种比线性表 和树更加复杂的数据结构，而树实际上是一种特殊形式的图 。第七章 图本章主要内容：1.图的定义及存储结构2.图的两种遍历及图的连通性3.拓扑排序和关键路径以及求最短路径的方法本章重点：1.图的各种存储结构及其构造算法2.图的两种搜索路径的遍历3.应用图的遍历算法求解各种简单路径问题第七章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性7.5 有向无环图及其应用7.6 最短路径7.1 图的定义和术语一、图的定义和术语二、抽象数据类型图的定义一、图的定义和术语7.1 图 的 定 义 和 术 语1图的定义图由两个集合V和E构成，记为G=(V,E)，其中V是顶点的有限集合，E是连接V中两个不同顶点(顶点对)的边的有限集合。2图的有关术语(1)顶点：图中的数据元素，v1,v2。(2)有向图：E中的顶点对是有序的，即每条边都是有方向的则称G为有向图。(1)(3)弧：有向图的边,(2)表示从v到w的一条弧。(3)(4)弧头：弧的终点w。弧尾：弧的起始点v。(5)无向图：E中顶点对是无序的，则称G为无向图。无向图中若存在(v,w)E,则必有(w,v)E。一、图的定义和术语7.1 图 的 定 义 和 术 语(6) 边：无向图的边。用n表示图中顶点数目，用e表示边或弧的数目。(7)完全图：对于无向图0en(n-1)/2,具有n(n-1)/2条边 的无向图称为完全图。 (8)有向完全图：对于有向图0en(n-1)，具有n(n-1)条 弧的有向图称为有向完全图。 (9)稀疏图：有很少条边或弧(e,。回答下列问题 ： a. 求与顶点b相关联的弧； b. 是否存在从顶点c到b的路径？ c. 求ID(d)、OD(d)、TD(d); d. 该有向图中是否是强连通图？一、图的定义和术语7.1 图 的 定 义 和 术 语解：a.与顶点b相关联的弧有两条：和；b.不存在从顶点c到b的路径；c.ID(d)=2;OD(d)=1,TD(d)=3; d.不是强连通图；一、图的定义和术语7.1 图 的 定 义 和 术 语72 图的存储结构一、邻接矩阵（数组表示法）二、邻接表三、十字链表四、多重邻接表一、邻接矩阵7.2 图 的 存 储 结 构邻接矩阵(Adjacency Matrix)是一种用来表示图中顶点间相邻关系的矩阵，是一种用边的集合表示图的方法。 1一维数组存储图的顶点 v0,v1,vn-1，用n阶矩阵A=(aij)表示图的边或弧，A的定义如下： (1) 若图为有权图，aij对应边或(vi,vj)的权值，(2) 若图为非权图，则aii=0;aij=1，当ij且或(vi,vj)存在时；aij=0，当ij且或(vi,vj)不存在时。称矩阵A为图的邻接矩阵。 当i=jWij 有或(vi,vj) 无aij=例1：如图所示的是有权图(网)的邻接矩阵： 0 1 2 3 4 0 2 7 1 1 2 5 3 4 3 4 7.2 图 的 存 储 结 构一、邻接矩阵例2：无权图的邻接矩阵： 1 2 3 4 1 0 1 1 1 2 1 0 0 1 3 1 0 0 1 4 1 1 1 07.2 图 的 存 储 结 构一、邻接矩阵2.邻接矩阵存储表示 #define INFINITY INT_MAX /最大值(定义infinity为最大值) #define MAX_VERTEX_NUM 20 / 最大顶点个数 typedef enum DG,DN,UDG,UDN GraphKind；/有向图，有向网，无 向图，无向网typedef struct ArcCell VRType adj； /VRType 是边(或弧)的类型。对无权图，用1 或0表示相邻否；对带权图，则为权值类型。 InfoType *Info； /该弧相关信息的指针 ArcCell，AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedrf struct VertexType vexsMAX_VERTEX_NUM；/顶点向量AdjMatrix arcs； /邻接矩阵Int vexnum,arcnum； /图的当前顶点数和弧数GraphKind kind； /图的种类标志 Mgraph； 7.2 图 的 存 储 结 构一、邻接矩阵3邻接矩阵的性质(1)在图中各顶点的序号确定后，图的邻接矩阵是唯一确 定的；(2)无向图和无向网的邻接矩阵是一个对称矩阵；(3)对于无向图，顶点的度是邻接矩阵中第i行(或第i列) 的非零元素个数之和；(4)对于有向图，第i行的非零元素个数之和为顶点vi的出 度，第j列的非零元素个数之和为顶点vj的入度。(5)无向图的边数等于邻接矩阵中非零元素个数之和的一 半，有向图的弧数等于邻接矩阵中非零元素个数之和。一、邻接矩阵7.2 图 的 存 储 结 构4邻接矩阵的特点(1)邻接矩阵可采用压缩存储(2)操作特点适于进行边或弧的删除和插入操作。但不易于进行顶 点的插入删除操作。一、邻接矩阵7.2 图 的 存 储 结 构5构造无向网的算法 status createUDN(Mgraph i的对称弧return OK; 一、邻接矩阵7.2 图 的 存 储 结 构1边链表依附于顶点V的所有边（或为弧尾的弧）以某种次序组成一 个链表，被称为顶点V的边链表。在边链表中，其结点结构 ：其中：adjvex域存放v的某个邻接顶点在顶点表中的序号；nextarc域存放指针，指向下一个边或弧的结点；info域存放边的权值。边链表表示依附某顶点vi的边信息(有向图是以顶点vi 为弧尾的弧)，其结点结构称为边结点。adjvex infonextarc有两部分：边链表：依附某顶点的边信息构成的单链表顶点表：用一维数组存储顶点本身及边链表的头指针二、邻接表7.2 图 的 存 储 结 构2顶点表用顺序存储方式存储图的顶点表v0,v1,v2,vn-1，每 个顶点的结构：data firstarc其中：data域放该顶点的名称；firstarc域是指针域，存放指向顶点相关边链表的第一个边结点的指针。 3邻接表由顺序存储的顶点表和链接存储的边链表构成的图的存储结构被称为邻接表。二、邻接表7.2 图 的 存 储 结 构例3：例1的邻接表：01234二、邻接表7.2 图 的 存 储 结 构例1 的逆邻接表01234二、邻接表7.2 图 的 存 储 结 构例2 邻接表：1234二、邻接表7.2 图 的 存 储 结 构4邻接表的存储表示 #define MAX_VERTEX_NUM 20 typedef struct ArcNodeint adjvex; /该弧指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针Infotype *info; /与该弧相关的信息(权)ArcNode;typedef struct Vnode vertexType data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针Vnode，AdjListMAX_VERTEX_NUM；二、邻接表7.2 图 的 存 储 结 构typedef structAdjList vertices；int vexnum,arcnum； /图的当前顶点数和弧数int kind； /图的种类标志ALGraph;二、邻接表7.2 图 的 存 储 结 构5邻接表的性质(1)图的邻接表表示不唯一的，它与边结点的次序有关；(2)无向图的邻接表中第i个顶点的度为第i个链表中结点的个数；(3)有向图的邻接表中第i个链表的结点的个数是第i个顶点的出度；而第i个顶点的入度需遍历整个链表，采用逆邻接表,建立一个以vi顶点为头的弧的表。(4)无向图的边数等于邻接表中边结点数的一半，有向图的弧数等于邻接表中边结点数。二、邻接表7.2 图 的 存 储 结 构6邻接表的特点(1)对于顶点多边少的图采用邻接表存储节省空间；(2)容易找到任一顶点的第一个邻接点和下一个邻接点 ，但要判定任意两个顶点之间是否有边或弧相连，则 需搜索第i个或第j个链表。二、邻接表7.2 图 的 存 储 结 构练习题：已知无向图G的邻接表如下，画出无向图G 。 12 3 4 5答案：十字链表是有向图另一种链式存储结构。是将有向 图的邻接表和逆邻接表结合起来得到的一种链表。 包含弧结点和顶点结点。 1弧结点 有五个域：三、十字链表tailvexheadvexhlinktlinkinfo其中：tailvex是尾域，指示弧尾顶点在图中的位置；headvex是头域，指示弧头顶点在图中的位置；hlink链域，指向弧头相同的下一条弧；tlink链域，指向弧尾相同的下一条弧；info域指向该弧的相关信息。 弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上 。 7.2 图 的 存 储 结 构2顶点结点顶点结点为弧结点构成的链表的头结点，由三个域组成。data firstinfirstout其中：data域存储和顶点相关的信息，如顶点的名称等；firstin链域指向以该顶点为弧头的第一个弧结点；firstout链域指向以该顶点为弧尾的第一个弧结点。 三、十字链表7.2 图 的 存 储 结 构例4 : 图的十字链表.三、十字链表7.2 图 的 存 储 结 构tailvexheadvexhlinktlinkinfo data firstinfirstout3十字链表的存储表示 #define MAX_VEX_NUM 20 typedef struct ArcBoxint tailvex,headvex; /该弧的尾和头顶点的位置struct ArcBox *hlink, *tlink; /分别为弧头相同和 弧尾相同的弧的链域Infotype *info /该弧相关信息的指针ArcBox; typedef struct VexNode Vertextype data;ArcBox *firstin, *firstout; /分别指向该顶点第一条入弧(以该点为弧头)和出弧(以该点为弧尾)VexNode;三、十字链表7.2 图 的 存 储 结 构typedef struct VexNode xlistMAX_VERTEX_NUM; /顶点结点数组int vexnum,arcnum; /有向图的当前顶点数和弧数OLGraph;在十字链表中既容易找到以vi为尾的弧，也容易找到以vi 为头的弧，因而容易求得顶点的出度和入度 。三、十字链表7.2 图 的 存 储 结