存储结构
用二维数组 存储, 表示顶点 i 与 j 之间有边。
优点:判断两顶点是否邻接 。缺点:空间 ,适合稠密图。
#define MaxVertexNum 100
typedef struct {
int edges[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
int n, e; // 顶点数、边数
} MGraph;
每个顶点用一个链表存储其所有邻接点。
优点:空间 ,适合稀疏图。缺点:判断邻接需遍历链表。
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。
最终答案:
C(2e)。
习题 2
邻接矩阵和邻接表各自的优缺点是什么?
解题思路:
本题考查图的两种存储结构的优缺点对比。答题时围绕两个关键操作——判断两顶点是否邻接、遍历某顶点的全部邻接点——分别评估两种结构的时间与空间代价,并给出适用场景。
详细步骤:
- 邻接矩阵的优点:判断两顶点是否邻接只需直接查表,为 ,且实现简单;缺点:空间开销为 ,对稀疏图浪费较大,适合稠密图。
- 邻接表的优点:空间开销为 ,节省存储空间;缺点:判断两顶点是否邻接需要遍历链表,适合稀疏图。
- 结论:边数接近顶点数平方的稠密图宜用邻接矩阵,边数远小于顶点数平方的稀疏图宜用邻接表。
最终答案:
邻接矩阵:优点——判断两顶点是否邻接 O(1)、实现简单;缺点——空间 O(n²),浪费大,适合稠密图。邻接表:优点——空间 O(n+e),节省空间;缺点——判断邻接需遍历链表,适合稀疏图。
