存储结构

邻接矩阵

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

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

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

邻接表

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

优点:空间 O(n+e)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

邻接表无向图边表结点存储空间

解题思路:

本题考查邻接表中边表结点的个数。关键在于弄清无向图的一条边在邻接表里要登记几次——每个端点的边表中各存一次。

详细步骤:

  1. 邻接表为每个顶点建立一个边表,用链表记录与该顶点相连的所有邻接点。
  2. 在无向图中,一条边 (u,v)(u, v) 需要在顶点 uu 的边表和顶点 vv 的边表中各登记一次,因此共占用两个边表结点。
  3. 共有 ee 条边,故边表结点总数为 2e2e,对应选项 C。

最终答案:

C(2e)。

习题 2

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

邻接矩阵邻接表存储空间适用场景

解题思路:

本题考查图的两种存储结构的优缺点对比。答题时围绕两个关键操作——判断两顶点是否邻接、遍历某顶点的全部邻接点——分别评估两种结构的时间与空间代价,并给出适用场景。

详细步骤:

  1. 邻接矩阵的优点:判断两顶点是否邻接只需直接查表,为 O(1)O(1),且实现简单;缺点:空间开销为 O(n2)O(n^2),对稀疏图浪费较大,适合稠密图。
  2. 邻接表的优点:空间开销为 O(n+e)O(n+e),节省存储空间;缺点:判断两顶点是否邻接需要遍历链表,适合稀疏图。
  3. 结论:边数接近顶点数平方的稠密图宜用邻接矩阵,边数远小于顶点数平方的稀疏图宜用邻接表。

最终答案:

邻接矩阵:优点——判断两顶点是否邻接 O(1)、实现简单;缺点——空间 O(n²),浪费大,适合稠密图。邻接表:优点——空间 O(n+e),节省空间;缺点——判断邻接需遍历链表,适合稀疏图。

发现内容有问题?

告诉我们哪里需要改进。