# 图的存储及基本操作   图的存储必须要完整、准确的反映顶点集和边集的信息。主要的存储方式有两种：邻接矩阵 和 邻接表。前者属于图的顺序存储结构，后者属于图的链式存储结构。 ## 邻接矩阵法   所谓邻接矩阵存储，是指**用一个一维数组存储图中顶点的信息**，**用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）**，存储顶点之间邻接关系的二维数组称为**邻接矩阵**。   结点数为 n 的 图 G = （V,E）的邻接矩阵A 是 n\*n的。将G的顶点编号为V1，V2，，，Vn。 $$ A\[i]\[j] = \begin{cases} 1,\quad 若（V\_i,V\_j）或\是E(G)中的边\\ 0, \quad 若（V\_i,V\_j）或\不是E(G)中的边 \end{cases} $$   对于带权树而言，若顶点Vi 和 Vj 之间有边相连，则邻接矩阵中对应的项存放着边相对应的权值，若顶点之间不相连，则用 **∞**来代表两个顶点之间不存在边： $$ A\[i]\[j] = \begin{cases} W\_{ij},\quad 若（V\_i,V\_j）或\是E(G)中的边\\ 0或\infty, \quad 若（V\_i,V\_j）或\不是E(G)中的边 \end{cases} $$ ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/邻接矩阵.png)   **图的邻接矩阵存储结构定义如下：** ```cpp #define MaxVertexNum 100 //顶点数目的最大值 typedef char VerterType; //顶点的数据类型 typedef int EdgeType; //带权图中边上权值的数据类型 typedef struct{ VertexType Vex[MaxVertexNum]; //顶点表 EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表 int vexnum,arcnum; //图的当前顶点数和弧数 }MGraph; ```   注：邻接矩阵表示法的空间复杂度为0（n2）,其中n为图的顶点数。   **图的邻接矩阵表示法的特点：** 1. 无向图的邻接矩一定是对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。 2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第 i 个顶点的度。 3. 对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第 i 个顶点的出度（或入度）。 4. 用邻接矩阵法存储图，很容易确定图中任意两顶点之间是否有边相连。但是，要确定图中有多少边，则必须按照行，按列，对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。 5. 稠密图适合用邻接矩阵法表示。 6. 设图G中的邻接矩阵为A，An 的元素Aij 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目。 ## 邻接表法   当一个图为稀疏图时，使用邻接矩阵表示法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。   **邻接表**：对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点的边，这个单链表就称为顶点的的边表。   边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点， ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/顶点表和边表结点结构.jpg)   顶点表结点由 顶点域（data）和指向第一条邻接边的指针（firstarc）构成，边表（邻接表）结点由 邻接点域（adjvex）和 指向下一条邻接边的指针域（nextarc）构成。   无向图和有向图的邻接表的实例如下： ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/邻接表.jpg)   图的邻接表存储结构定义如下： ```cpp #define MaxVertexNum 100 //图中最大顶点数 typedef struct ArcNode{ //边表结点 int adjvex; //该弧所指向的顶点的位置 struct ArcNode *next; //指向下一条弧的指针 //InfoType info //网的边权值 }ArcNode; typedef struct VNode{ //顶点表 VertexType data; //顶点信息 ArcNode *first; //指向第一条依附该结点的弧的指针 }VNode,AdjList[MaxVertexNum]; typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; //图的顶点和弧数 }ALGraph; //以邻接表存储的图类型 ```   图的邻接表存储方法的特点： 1. 若G为无向图，则所需的存储空间为O（|v|+2|E|）；若G为有向图，则所需的存储空间为O（|v|+|E|）。 2. 对于稀疏图，采用邻接表表示将极大地节省存储空间 3. 在邻接表中，给定一顶点，能很容易地找出他的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同操作则需要扫描一行，花费的时间为O（n）。但是，若要确定给定的两个顶点间是否存在边，则需在邻接矩阵中可以立刻查到，而在邻接表中则要在相应结点对应的边表中查找另一结点，效率低下。 4. 在有向图的邻接表表示中，求一个给定结点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。 5. 图的邻接表表示并不唯一，因此在每个定点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。 ## 十字链表   十字链表是有向图的一种链式存储结构。在十字链中，对应有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下： ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/十字链表结点结构.jpg)   弧结点中有5个域：尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这个两个顶点在图中的位置；链域hlink 指向弧头相同的下一条弧；链域tlink指向弧尾相同的下一条弧；info域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。   顶点结点中有3个域：data域存放顶点相关的数据信息，如顶点名称；firstin 和 firstout 两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。 ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/十字链表.jpg)   图的十字链表存储结构定义如下： ```cpp #define MaxVertexNum 100 //图中顶点的最大数量 typedef struct ArcNode { //边表结点 int tailvex, headvex; //该弧的头尾结点 struct ArcNode *hlink, *tlink; //分别指向弧头相同和弧尾相同的结点 //InfoTyped Info; //相关信息指针 }ArcNode; typedef struct VNode{ //顶点表信息 VertexType data; //顶点信息 ArcNode *firstin, *firstout; //指向第一条入弧和出弧 }VNode; typedef struct{ VNode xlist[MaxVertexNum]; //邻接表 int vexnum,arcnum; //图的顶点数和弧数 }GLGraph; //GLGraph 是以十字邻接存储的图类型 ```   在十字链表中，既容易找到Vi为尾的弧，又容易找到Vi为头的弧，因而容易求得顶点的出度和入度。   图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。 ## 邻接多重表   邻接多重表是无向图的另一种链式存储结构。   在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边指向删除等操作时，需要分别在两个顶点的边表中遍历，效率低下。   与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下。 ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/邻接多重表结点结构.png)   其中，mark为标志域，可用以标记该条边是否被搜索过；ivex 和 jvex 为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。   每个顶点也用一个结点表示，它是由由以下的两个域表示： ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/十字链表结点.jpg)   其中，data域存储该结点的相关信息，firstedge域指示第一条依附于该顶点的边。   在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边界点同时链接在两个链表中。 ![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/邻接多重表.png)   图的邻接多重表存储结构定义如下： ```cpp #define MaxVertexNum 100 //图中顶点数目的最大值 typedef struct ArcNode{ //边表结点 bool mark; //访问标志 int ivex, jvex; //分别指向该弧的两个结点 struct ArcNode *ilink, *jlink; //分别指向两个顶点的下一条边 //InfoType info; //相关信息指针 }ArcNode; typedef struct VNode{ //顶点表结点 VertexType data; //顶点信息 ArcNode *firstedge; //指向第一条依附顶点的边 }VNode; typedef struct{ VNode adjmulist[MaxVertexNum]; //邻接表 int vexnum,arcnum; //图的顶点数和弧数 }AMLGraph; //AMLGraph是以邻接多重表存储的图类型 ``` ## 图的基本操作   图的基本操作是独立于图的存储结构的。而对于不同的存储方式，操作算法的具体实现会有不同的性能。   图的基本操作主要包括： 1. Adjacent（G,x,y）：判断图G是否存在边或（x，y）。 2. Neighbors（G,x）：列出图G中与结点x邻接的边。 3. InsertVertex（G,x）：在图中插入顶点x。 4. DeleteVertex（G,x）：在图中删除顶点x。 5. AddEdge（G,x,y）：若无向边（x，y）或有向边不存在，则向图G中添加该边 6. RemoveEdge（G，x，y）：若无向边（x，y）或有向边存在，则从图G中删除该边 7. FirstNeighbor（G，x）：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回 - 1 8. NextNeighbor（G，x，y）：假设图G中顶点y是顶点x的一个邻接点，返回出y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回 -1 9. Get\_edge\_value（G，x，y）：获取图G中边或（x，y）对应的权值 10. Set\_edge\_value（G，x，y，v）：设置图G中边或（x，y）对应的权值为v 11. 图的遍历算法：深度优先遍历和广度优先遍历 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://xiuxin.gitbook.io/datastructre/tu/tu-de-cun-chu-ji-ji-ben-cao-zuo.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.