图的存储结构

一、邻接矩阵

定义

用一个二维数组表示图中顶点之间的邻接关系。

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

无权图

$$A[i][j] = \begin{cases} 1, & (v_i, v_j) \in E \text{ 或 } <v_i, v_j> \in E \\ 0, & \text{其他} \end{cases}$$

带权图

$$A[i][j] = \begin{cases} w_{ij}, & (v_i, v_j) \in E \text{ 或 } <v_i, v_j> \in E \\ \infty, & \text{其他} \end{cases}$$

示例

     A --- B
     |   / |
     |  /  |
     C --- D

邻接矩阵：

    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  1  1 ]
C [ 1  1  0  1 ]
D [ 0  1  1  0 ]

特点

• 无向图：对称矩阵，可压缩存储上 / 下三角
• 空间复杂度：$O(|V|^2)$
• 适用：稠密图

基本操作复杂度

二、邻接表

定义

对每个顶点建立一个单链表，存储其所有邻接点。

// 边结点
typedef struct ArcNode {
    int adjvex;              // 邻接点下标
    struct ArcNode *next;    // 下一条边
    // InfoType info;        // 边权值
} ArcNode;

// 顶点结点
typedef struct {
    char data;               // 顶点信息
    ArcNode *first;          // 第一条边
} VNode;

// 邻接表
typedef struct {
    VNode vertices[MaxVertexNum];
    int vexnum, arcnum;
} ALGraph;

示例

     A --- B
     |   / |
     |  /  |
     C --- D

邻接表：

A → [B] → [C]
B → [A] → [C] → [D]
C → [A] → [B] → [D]
D → [B] → [C]

特点

• 无向图：边结点数 $= 2|E|$
• 有向图：边结点数 $= |E|$
• 空间复杂度：$O(|V| + |E|)$
• 适用：稀疏图

基本操作复杂度

三、逆邻接表

对有向图，每个顶点的链表存储指向该顶点的边。

A ← B
A ← C
B ← C
B ← D
C ← D

逆邻接表：

A → [B] → [C]      ← 指向A的边
B → [C] → [D]      ← 指向B的边
C → [D]            ← 指向C的边
D                  ← 指向D的边

四、十字链表（有向图）

typedef struct ArcBox {
    int tailvex, headvex;         // 弧尾、弧头
    struct ArcBox *hlink, *tlink; // 同弧头、同弧尾链
    // InfoType info;
} ArcBox;

typedef struct VexNode {
    char data;
    ArcBox *firstin, *firstout;  // 入弧、出弧
} VexNode;

特点：

• 结合邻接表和逆邻接表
• 方便求入度和出度
• 空间：$O(|V| + |E|)$

五、邻接多重表（无向图）

typedef struct ArcNode {
    int ivex, jvex;                // 依附的两个顶点
    struct ArcNode *ilink, *jlink; // 依附于ivex、jvex的下一条边
    // InfoType info;
} ArcNode;

typedef struct {
    char data;
    ArcNode *firstedge;
} VexNode;

特点：

• 每条边只存储一次
• 方便删除边

例 1：邻接矩阵构造

有向图：

A → B → C
↑       ↓
← ← ← D

邻接矩阵：

    A  B  C  D
A [ 0  1  0  0 ]
B [ 0  0  1  0 ]
C [ 0  0  0  1 ]
D [ 1  0  0  0 ]

例 2：邻接表构造

无向图：

0 --- 1
|   / |
|  /  |
2 --- 3

邻接表：

0 → [1] → [2]
1 → [0] → [2] → [3]
2 → [0] → [1] → [3]
3 → [1] → [2]

例 3：入度出度计算

有向图邻接表：

A → [B] → [C]
B → [C]
C → [A]
D → [A] → [B]