定义图、顶点、边、路径和连通性,比较邻接矩阵、邻接表、十字链表与邻接多重表的表示方法和操作代价。

# 一、图的基本概念

图由顶点集合 VV 和边集合 EE 构成,记作 G=(V,E)G=(V,E)。边连接顶点;若边有方向,称有向图,否则称无向图。带权图的边还关联一个权值,可表示距离、费用或持续时间。

概念含义
无向边无序顶点对 {u,v}\{u,v\},从 uu 到 vv 与从 vv 到 uu 等价
有向边或弧有序顶点对 ⟨u,v⟩\langle u,v\rangle,方向从 uu 指向 vv
顶点的度无向图中与顶点关联的边数
入度、出度有向图中以顶点为终点、以顶点为起点的弧数
路径沿边依次经过的顶点序列,路径长度通常按边数计
回路起点和终点相同的路径
连通图无向图中任意两顶点间均有路径
强连通图有向图中任意两顶点间均可互相到达
连通分量无向图的极大连通子图
有向无环图(DAG)不含有向回路的有向图

简单图不含自环和重边。含 nn 个顶点的简单无向完全图有 n(n−1)/2n(n-1)/2 条边;若为不含自环的简单有向完全图,则有 n(n−1)n(n-1) 条弧。

无向图满足握手定理:

∑v∈Vdeg⁡(v)=2∣E∣.\sum_{v\in V}\deg(v)=2|E|.

有向图中所有顶点入度之和与出度之和都等于弧数:

∑v∈Vdeg⁡−(v)=∑v∈Vdeg⁡+(v)=∣E∣.\sum_{v\in V}\deg^-(v) =\sum_{v\in V}\deg^+(v)=|E|.

# 二、邻接矩阵

若顶点编号为 00 到 ∣V∣−1|V|-1,邻接矩阵用二维数组 AA 保存边。无向图的矩阵关于主对角线对称;有向图中 A[i][j]A[i][j] 表示从顶点 ii 到顶点 jj 是否有弧或该弧权值。

1
2
3
4
5
6
7
#define MAX_VERTEX_NUM 100
#define INF 0x3f3f3f3f

typedef struct {
int vexnum;
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
} MatrixGraph;

无权图可用 0/10/1 表示无边与有边;带权图不宜简单用 00 表示无边,因为零权边可能合法。通常令 A[i][i]=0A[i][i]=0,无边处为 INF,其余位置存权值。

邻接矩阵判断两点是否相邻为 O(1)O(1),枚举某顶点的所有邻接点需要 O(∣V∣)O(|V|),空间复杂度为 O(∣V∣2)O(|V|^2)。它适合稠密图,也便于实现 Floyd 等需要访问任意顶点对的算法。

# 三、邻接表

邻接表为每个顶点维护一条链表或动态数组,保存从该顶点出发的邻接点。稀疏图中仅需保存顶点和边,空间复杂度为 O(∣V∣+∣E∣)O(|V|+|E|)。对无向边 {u,v}\{u,v\},通常在 uu 和 vv 的邻接表中各记录一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct ArcNode {
int adjvex;
int weight;
struct ArcNode *next;
} ArcNode;

typedef struct {
int data;
ArcNode *firstArc;
} VertexNode;

typedef struct {
VertexNode vertices[MAX_VERTEX_NUM];
int vexnum;
int arcnum;
} AdjListGraph;

在有向图中,顶点 uu 的邻接表记录从 uu 出发的弧,因此扫描它可得到出度和后继;求入度通常需扫描所有邻接表,或额外保存逆邻接表。无向图的边结点总数通常为 2∣E∣2|E|,但逻辑边数仍是 ∣E∣|E|。

表示方法空间判断任意两点相邻枚举顶点邻居适用场景
邻接矩阵O(V2)O(V^2)O(1)O(1)O(V)O(V)稠密图,频繁查询任意顶点对
邻接表O(V+E)O(V+E)通常需扫描邻接表O(deg⁡(v))O(\deg(v))稀疏图,频繁遍历邻接边

# 四、其他链式存储

  • 十字链表用于有向图。弧结点同时链接在弧尾的出边链和弧头的入边链上,便于分别遍历顶点的出边与入边。
  • 邻接多重表用于无向图。每条无向边只保存一个边结点,并通过两个链接分别接入两个端点的边链,适合边的插入、删除和遍历。
  • 边集数组直接保存 (u,v,w)(u,v,w) 边记录,适合按权值排序的 Kruskal 算法,但枚举单个顶点邻居通常需要扫描所有边。

# 五、考场检查清单

  1. 邻接矩阵的行和列分别表示起点、终点;有向图不要误把矩阵写成对称。
  2. 无向图邻接表中一条逻辑边通常占两个边结点;边数仍按逻辑边计。
  3. 带权图中用 INF 表示无边时,初始化对角线为 00。
  4. 邻接矩阵空间与顶点数平方相关,邻接表空间与顶点和边数之和相关。
  5. 有向图邻接表自然给出出边;入边需要反向组织或额外遍历。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝