存储结构

邻接矩阵

用二维数组 $A[n][n]$ 存储， $A[i][j]=1$ 表示顶点 i 与 j 之间有边。

优点：判断两顶点是否邻接 $O(1)$ 。缺点：空间 $O(n^2)$ ，适合稠密图。

#define MaxVertexNum 100
typedef struct {
    int edges[MaxVertexNum][MaxVertexNum];  // 邻接矩阵
    int n, e;  // 顶点数、边数
} MGraph;

邻接表

每个顶点用一个链表存储其所有邻接点。

优点：空间 $O(n+e)$ ，适合稀疏图。缺点：判断邻接需遍历链表。

typedef struct ArcNode {       // 边表结点
    int adjvex;                // 邻接点下标
    struct ArcNode *next;
} ArcNode;

typedef struct VNode {         // 顶点表结点
    int data;
    ArcNode *first;            // 指向第一条边
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;
    int n, e;
} ALGraph;

其他存储

十字链表：有向图专用，同时记录入边和出边
邻接多重表：无向图专用，每条边只存一次

习题

习题 1

用邻接表存储有 n 个顶点、e 条边的无向图，则其邻接表中边表结点的个数为（）

A. n B. e C. 2e D. n+e

答案与解析

答案：C

解析：无向图中每条边在邻接表中被存储两次（两个端点各记录一次），所以边表结点个数为 2e。

习题 2

邻接矩阵和邻接表各自的优缺点是什么？

答案与解析

邻接矩阵：优点——判断两顶点是否邻接 O(1)、实现简单；缺点——空间 O(n²)，浪费大，适合稠密图。

邻接表：优点——空间 O(n+e)，节省空间；缺点——判断邻接需遍历链表，适合稀疏图。

上一章节基本概念图的定义、常用术语与性质。

下一章节图的遍历图的广度优先搜索（BFS）与深度优先搜索（DFS）。