602 图的存储和基本操作

邻接矩阵法

定义与结构

邻接矩阵是用二维数组存储图的方法。对于 n 个顶点的图 G=(V,E)，邻接矩阵 A 是 n×n 的矩阵，其中：

• 对于无权图：$A[i][j]=\{\begin{array}{ll}1& 若(v_i,v_j)\in E\\ 0& 若(v_i,v_j)\notin E\end{array}$
• 对于有权图：$A[i][j]=\{\begin{array}{ll}{w}_{ij}& 若(v_i,v_j)\in E\\ \infty \text{或}0& 若(v_i,v_j)\notin E\end{array}$ 索引方式： 直接通过数组下标访问，时间复杂度 O(1)。判断顶点 i 和 j 之间是否存在边，直接查看 A[i][j] 的值即可。

存储结构

#define MaxVertexNum 100
typedef struct {
    char vex[MaxVertexNum];          // 顶点表
    int edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵
    int vexnum, arcnum;              // 顶点数和弧数
} MGraph;

特点分析

优点：

• 直观简单，便于理解和实现
• 便于判断任意两个顶点间是否有边：O(1)
• 便于计算顶点的度：遍历对应行或列
• 适合稠密图的存储

缺点：

• 空间复杂度为 O(n²)，不适合稀疏图
• 插入和删除顶点操作复杂度高
• 无法存储重复边

性质

• 无向图的邻接矩阵是对称矩阵
• 顶点 $v_i$ 的度 = 第 i 行元素之和
• 有向图中，顶点 $v_i$ 的出度 = 第 i 行元素之和，入度 = 第 i 列元素之和

邻接表法

定义与结构

邻接表是图的一种链式存储结构，由顶点表和边表组成：

• 顶点表：存储顶点信息和指向第一条邻接边的指针
• 边表：存储与顶点相邻的所有顶点信息

存储方式： 为每个顶点维护一个链表，存储该顶点的所有邻接顶点。通常用数组存储各顶点的链表头指针，每个链表节点包含邻接顶点编号和边权值（如果有）。

索引方式： 先通过顶点编号找到对应链表，再遍历链表查找目标顶点。查找特定边的时间复杂度为 O(degree)，其中 degree 是顶点的度数。

存储结构

typedef struct ArcNode {
    int adjvex;                    // 邻接点域
    struct ArcNode *next;          // 链域
    // int weight;                 // 权值域（有权图）
} ArcNode;
 
typedef struct VNode {
    int data;                      // 顶点信息
    ArcNode *first;               // 指向第一条邻接弧
} VNode, AdjList[MaxVertexNum];
 
typedef struct {
    AdjList vertices;             // 邻接表
    int vexnum, arcnum;          // 顶点数和弧数
} ALGraph;

特点分析

优点：

• 空间复杂度为 O(|V|+|E|)，适合稀疏图
• 便于遍历顶点的所有邻接点
• 便于插入和删除边
• 可以存储重复边

缺点：

• 判断两个顶点间是否有边需要遍历：O(度)
• 不便于计算有向图顶点的入度

度的计算

• 无向图：顶点 $v_i$ 的度 = 第 i 个链表的结点个数
• 有向图：顶点 $v_i$ 的出度 = 第 i 个链表的结点个数

十字链表法

定义与结构

十字链表是有向图的存储方法，结合了邻接表和逆邻接表的优点。每个弧结点有 5 个域：尾域、头域、头链域、尾链域、权值域。

存储方式： 专门用于有向图，每个顶点有两个链表：出边表和入边表。每条边用一个节点表示，该节点同时链接在起点的出边表和终点的入边表中。

索引方式：

• 查找顶点 v 的所有出边：遍历 v 的出边表
• 查找顶点 v 的所有入边：遍历 v 的入边表
• 每个边节点包含两个顶点和两个指针：边节点的弧起点（弧尾）和弧终点（弧头）；指向同一起点的下一条出边、指向同一终点的下一条入边

存储结构

typedef struct ArcBox {
    int tailvex, headvex;         // 弧的尾和头顶点位置
    struct ArcBox *hlink, *tlink; // 分别指向头相同和尾相同的下一条弧
    // int weight;                // 权值域
} ArcBox;
 
typedef struct VexNode {
    int data;                     // 顶点信息
    ArcBox *firstin, *firstout;   // 分别指向第一条入弧和出弧
} VexNode;
 
typedef struct {
    VexNode xlist[MaxVertexNum];  // 表头向量
    int vexnum, arcnum;          // 顶点数和弧数
} OLGraph;

特点分析

优点：

• 既能快速找到以 $v_i$ 为尾的弧，也能快速找到以 $v_i$ 为头的弧
• 便于计算顶点的入度和出度
• 便于插入和删除弧

缺点：

• 结构复杂，实现难度大
• 只适用于有向图
• 存储密度相对较低

邻接多重表

定义与结构

邻接多重表是无向图的存储方法，解决了邻接表中边信息冗余存储的问题。每条边只存储一次。

（类似于邻接表，核心思想：将邻接表中重复存储的边信息合并，使一个边节点同时服务于该边的两个端点顶点。）

存储方式： 专门用于无向图，每条边只用一个节点表示，但该节点同时出现在两个端点的邻接表中。边节点包含两个顶点信息和两个指针，分别指向与这两个顶点相关的下一条边。

索引方式： 从顶点的边链表开始，通过边节点中的指针遍历该顶点的所有关联边。每个边节点根据当前访问的顶点，选择相应的 ” 下一条边 ” 指针。

存储结构

typedef struct EBox {
    int mark;                     // 访问标记
    int ivex, jvex;              // 边依附的两个顶点位置
    struct EBox *ilink, *jlink;   // 分别指向依附于ivex和jvex的下一条边
    // int weight;               // 权值域
} EBox;
 
typedef struct VexBox {
    int data;                     // 顶点信息
    EBox *firstedge;             // 指向第一条依附该顶点的边
} VexBox;
 
typedef struct {
    VexBox adjmulist[MaxVertexNum]; // 表头向量
    int vexnum, edgenum;            // 顶点数和边数
} AMLGraph;

特点分析

优点：

• 每条边只存储一次，节省存储空间
• 便于对边进行操作（如删除边）
• 支持边的标记操作

缺点：

• 结构复杂，实现难度大
• 只适用于无向图

图的基本操作

基本操作接口

1. Adjacent(G,x,y) - 判断图 G 中顶点 x 和 y 是否邻接
2. Neighbors(G,x) - 列出图 G 中与顶点 x 邻接的边
3. InsertVertex(G,x) - 在图 G 中插入顶点 x
4. DeleteVertex(G,x) - 从图 G 中删除顶点 x
5. AddEdge(G,x,y) - 若无向边 (x,y) 或有向边<x,y>不存在，则添加该边
6. RemoveEdge(G,x,y) - 若无向边 (x,y) 或有向边<x,y>存在，则删除该边
7. FirstNeighbor(G,x) - 求图 G 中顶点 x 的第一个邻接点
8. NextNeighbor(G,x,y) - 假设图 G 中顶点 y 是顶点 x 的邻接点，返回除 y 外顶点 x 的下一个邻接点
9. Get_edge_value(G,x,y) - 获取图 G 中边 (x,y) 或<x,y>对应的权值
10. Set_edge_value(G,x,y,v) - 设置图 G 中边 (x,y) 或<x,y>对应的权值为 v

操作复杂度比较

操作	邻接矩阵	邻接表
查找边 (x,y)	O(1)	O(度)
插入边	O(1)	O(1)
删除边	O(1)	O(度)
求顶点度	O(n)	O(度)
空间复杂度	O(n²)	O(n+e)

实现要点

• 邻接矩阵法适合稠密图，操作简单但空间开销大
• 邻接表法适合稀疏图，空间效率高但某些操作复杂度较高
• 十字链表和邻接多重表适合特定场景，结构复杂但功能强大
• 选择存储方法应根据图的稠密程度、操作特点和空间要求综合考虑