圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台第7章图7.1复习笔记一、图的定义和术语1．定义图G由顶点集V和边集E组成，记做G＝（V，E）。其中，V＝{v1，v2，…，vn}，|V|表示图G中顶点的个数；E＝{（u，v）|u∈V，v∈V}，|E|表示图G中边的数目。2．基本术语（1）顶点集和边集：顶点的有穷非空集合为顶点集V；两个顶点之间关系的集合为边集E。（2）有向图：若E是有向边（弧）的有限集合时，图G为有向图；弧
A[i][j]??
??0当(vi,vj)或?vi,vj?不是E(G)的边
对于带权有向图则有以下关系（式中wij为边的权值）：当(vi,vj)或?vi,vj?是E(G)的边??wijA[i][j]????0或?当(vi,vj)或?vi,vj?不是E(G)的边【注意】①无向图的邻接矩阵是对称矩阵；②图G的顶点个数为|V|时，邻接矩阵表示法实现的算法时间复杂度为O（|V|2）；③无向图中邻接矩阵的第i行非零元素的个数是第i个顶点的度；有向图中邻接矩阵的第i行（或第i列）非零元素或非∞元素的个数为第i个顶点的出度（或入度）。2．邻接表在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于点vi
的边，该单链表称为顶点vi的边表。表中的每个结点由三个域组成，其中邻接点域（adjvex）指示与顶点vi邻接的点在图中的位置；链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等；表结点结构如下所示：表结点3/138圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台每个链表上附设一个头结点，设置数据域（data）存储相关信息，设置链域（firstarc）指向链表中第一个结点，头结点结构如下所示：头结点【注意】①用邻接表存储图时，若图G为无向图，则需存储空间为O（|V|＋2|E|）；若图G为有向图，则需存储空间为O（|V|＋|E|）；②在邻接表存储方式中，较为容易找到某一顶点的所有邻边；③无向图的邻接表中，顶点vi的度为第i个链表中结点的个数；④有向图的邻接表中，顶点vi的出度为第i个链表中结点的个数，求其入度则需遍历整个领接表；⑤逆邻接表：任一表头结点下的边结点的数量是有向图中该结点入度的弧的数量，与邻接表相反；⑥稀疏图采用邻接表更为节省空间。3．十字链表十字链表是有向图的一种链式存储结构，十字链表中，对应于有向图中的每一条弧有一个结点，每个顶点也有一个结点。弧结点中tailvex（尾域）和headvex（头域）分别指示弧尾和弧头两个顶点的位置，hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧，弧结点的结构如下所示：弧结点顶点结点中data存放顶点相关的信息，firstin和firstout分别指向以该顶点为弧头或弧4/138圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台尾的第一个弧结点，顶点结点结构如下所示：顶点结点只要输入n个顶点信息和e条弧的信息，便可建立该有向图的十字链表，有向图7-1（a）的十字链表如图7-1（b）所示。图7-1【注意】有向图的十字链表示例①建立十字链表和邻接表的时间复杂度是相同的；②十字链表容易直接求出顶点vi的出度和入度；③图的十字链表不唯一，但确定的十字链表可以画出唯一图。4．邻接多重表邻接多重表是无向图的一种链式存储结构。在邻接多重表中，每一条边用一个结点表示，其中，mark标记该边是否被访问过，ivex和jvex表示该边依附的两个顶点在图中的位置，ilink和jlink分别指向下一条依附于顶点ivex和jvex的边；每一个顶点也用一个结点表示，data域存储该顶点的相关信息，firstedge域指示第一条依附于顶点的边，两者结构如下所示：边结点5/138
严蔚敏《数据结构》配套复习资料(7-9章)【圣才出品】
