数据结构:图及其抽象数据类型

1 图的基本概念

1.1 图的定义和术语

图 (Graph) 是一种数据结构,由顶点 (Vertex) 集合和描述它们之间关系的集合组成。顶点之间的关系称为边 (Edge)

一个图 $G$ 记为 $G=(V, E)$,$V$ 是顶点 $V_i$ 的有限集合,$n$ 为顶点数,$E$ 是边的有限集合:

  • $V=${$V_i|V_i \in$ 某个数据集合}; $0 \leq i < n$, $n \geq 0$
  • $E=${$(V_i, V_j) | V_i,V_j \in V$} 或 $E=${$\lang V_i, V_j\rang | V_i,V_j \in V$}; $0 \leq i,j < n$, $i \neq j$

1.1.1 无向图

无向图 (Undirected Graph) 中的边没有方向,每条边用两个顶点的无序对表示,如 $(V_i, V_j)$ 和 $(V_j, V_i)$ 都表示连接顶点 $V_i$ 和 $V_j$ 之间的一条边。如下图所示:

无向图 (Undirected Graph)

无向图 $G_1$ 的顶点集合 $V$ 和边集合 $E$ 分别为:

  • $V(G_1) = ${$A,B,C,D,E,F$}
  • $E(G_1) = ${$(A,B)$,$(A,C)$,$(A,D)$,$(B,C)$,$(B,E)$,$(C,D)$,$(C,E)$,$(D,E)$,$(D,F)$}

1.1.2 有向图

有向图 (Directed Graph) 中的边有方向,每条边用两个顶点的有序对表示,如 $\lang V_i, V_j \rang$ 表示从顶点 $V_i$ 到 $V_j$ 的一条有向边,$V_i$ 是边的起点,$V_j$ 是边的终点。因此,$\lang V_i, V_j \rang$ 和 $\lang V_j, V_i \rang$ 表示方向不同的两条边。

下图是一个有向图示例,图中箭头表示边的方向,箭头从起点指向终点:

有向图 (Directed Graph)

$G_2$ 的顶点集合 $V$ 和边集合 $E$ 分别为:

  • $V(G_2) = ${$A,B,C,D,E$}
  • $E(G_1) = ${$\lang A,B \rang$,$\lang A,E \rang$,$\lang B,C \rang$,$\lang B,D \rang$,$\lang C,E \rang$,$\lang D,C \rang$,$\lang D,E \rang$}

1.1.3 完全图

完全图 (Complete Graph) 是指图的边数达到最大值。$n$ 个顶点的完全图记为 $K_n$。

  • 无向完全图 $K_n$ 的边数为 $n*(n-1)/2$;
  • 有向完全图 $K_n$ 的边数为 $n * (n-1)$。

如下图所示:

完全图 (Complete Graph)

1.1.4 带权图

带权图 (Weighted Graph) 是指图中的边具有 权 (Weight) 值。在不同的应用中,权值可能具有不同的含义。例如,如果图表示城市,则边的权值可以表示两个城市间的距离、从一个城市到另一个城市所需的时间或代价等。带权图也被称为网络 (Network)。下图展示了一个带权图,其中边上的实数表示权值:

带权图 (Weighted Graph)

1.1.5 邻接顶点

若 $(V_i,V_j)$ 是无向图 $E(G)$ 中的一条边,则称 $V_i$ 和 $V_j$ 互为邻接顶点 (Adiacent Vertex),且边 $(V_i,V_j)$ 依附于顶点 $V_i$ 和 $V_j$,顶点 $V_i$ 和 $V_j$ 依附于边 $(V_i,V_j)$。

若 $\lang V_i,V_j \rang$ 是有向图 $E(G)$ 中的一条边,则称顶点 $V_i$ 邻接到顶点 $V_j$,顶点 $V_j$ 邻接自顶点 $V_i$,边 $\lang V_i,V_j \rang$ 与顶点 $V_i$ 和 $V_j$ 相关联。

1.2 顶点的度

顶点的度 (Degree) 是指与顶点关联的边数,记为 $degree(V_i)$。度为 0 的顶点称为孤立点,度为 1 的顶点称为悬挂点 (Pendant Node)

在有向图中:

  • 以 $V_i$ 为终点的边数称为 $V_i$ 的入度,记作作 $indegree(V_i)$;
  • 以 $V_i$ 为起点的边数称为 $V_i$ 的出度,记为 $outdegree(V_i)$。

有向图顶点的度是入度与出度之和,即 $degree(V_i) = indegree(V_i) + outdegree(V_i)$。

设图 $G$ 有 $n$ 个顶点、$e$ 条边。

  • 若 $G$ 是无向图,则边数 $e = \frac{1}{2} \displaystyle \sum_{i = 1}^{n} degree(V_i)$,即边数为所有顶点的度数之和的一半;
  • 若 $G$ 是有向图,则边数 $e = \displaystyle \sum_{i = 1}^{n} indegree(V_i) = \displaystyle \sum_{i = 1}^{n} outdegree(V_i)$,即所有顶点入度之和等于出度之和,且值等于边数。

1.3 子图

设图 $G = (V, E)$、$G’ = (V’, E’)$,若 $V’ \subseteq V$ 且 $E’ \subseteq E$,则称图 $G’$ 是 $G$ 的子图 (Subgraph)

  • 如果 $G’$ 是 $G$ 的子图,且 $G’ \neq G$,则称 $G’$ 是 $G$ 的真子图
  • 如果 $G’$ 是 $G$ 的子图,且 $V’ = V$,则称 $G’$ 是 $G$ 的生成子图 (Spanning Subgraph)

如下图所示:

子图 (Subgraph) 子图 (Subgraph)

1.4 路径

一个有 $n$ 个顶点的图 $G=(V,E)$,若 $(V_i,V_{p1})$、 $(V_{p1},V_{p2})$、…、$(V_{pm},V_{j})$,($0 \leq p1, p2,…,pm < n$) 都是 $E(G)$ 的边,则称顶点序列 $(V_i,V_{p1},V_{p2},…,V_{pm},V_j)$ 是从顶点 $V_i$ 到 $V_j$ 的一条路径 (Path)。若 $G$ 是有向图,则路径 $\lang V_i,V_{p1},V_{p2},…,V_{pm},V_j \rang$ 也是有向的,$V_i$ 为路径起点,$V_j$ 为终点。

简单路径 (Simple Path) 是指路径 $(V_1,V_2,…V_m)$ $(0 \leq m < n)$ 上各顶点互不重复。

回路 (Cycle Path) 是指起点和终点相同且长度大于 1 的简单回路,回路又称为

对于不带权的图,路径长度 (Path Length) 指该路径上的边数。对于带权图,路径长度指路径上个边的权值之和。

一个有向图 $G$ 中,若存在一个顶点 $V_0$,从 $V_0$ 有路径可以到达 $G$ 图中其他所有顶点,则称此有向图为有根的图。$V_0$ 也被称作图 $G$ 的

1.5 连通性

1.5.1 连通图和连通分量

在无向图 $G$ 中,若从顶点 $V_i$ 到 $V_j$ $(V_i \neq V_j)$ 有路径,则称 $V_i$ 和 $V_j$ 是连通的。若图 $G$ 中任意一对顶点 $V_i$ 和 $V_j$ 都是连通的,则称 $G$ 为连通图 (Connected Graph)

非连通图的极大连通子图称为该图的连通分量 (Connected Component)

1.5.2 强连通图和强连通分量

在有向图中,若在每一对顶点 $V_i$ 到 $V_j$ $(V_i \neq V_j)$ 之间都存在一条从 $V_i$ 到 $V_j$ 的路径,也存在一条从 $V_j$ 到 $V_i$ 的路径,则称该图是强连通图 (Strongly Connected Graph)

非强连通图的极大强连通子图称为该图的强连通分量 (Strongly Connected Component)

2 图的抽象数据类型

图的基本操作有:获得顶点数、获得顶点元素、插入顶点或边、删除顶点或边、遍历等。图的抽象数据类型 Graph<T> 声明如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 图的抽象数据类型
 * @param <T> 节点元素类型
 */
public interface Graph<T> {
    // 返回顶点数
    int vertexCount();
    // 返回顶点 Vi 元素
    T getVertex(int i);
    // 设置顶点 Vi 元素为 x
    void setVertex(int i, T x);
    // 插入元素值为 x 的顶点,并返回顶点序号
    int insertVertex(T x);
    // 删除顶点 Vi 及其关联的边
    void removeVertex(int i);
    // 返回 Vi 在 Vj 后的后继邻接顶点的序号
    int next(int i, int j);
    // 插入边 <Vi, Vj>,权值为 weight
    void insertEdge(int i, int j, int weight);
    // 删除边 <Vi, Vj>
    void removeEdge(int i, int j);
    // 返回 <Vi, Vj> 边的权值
    int weight(int i, int j);
    // 非联通图的一次深度优先搜索遍历,从顶点 Vi 出发
    void DFSTraverse(int i);
    // 非联通图的一次广度优先搜索遍历,从顶点 Vi 出发
    void BFSTraverse(int i);
    // 构造带权无向图的最小生成树,Prim 算法
    void minSpanTree();
    // 求带权图顶点 Vi 的单源最短路径,Dijkstra 算法
    void shortestPath(int i);
    // 求带权图每对顶点间的最短路径,Floyd 算法
    void shortestPath();
}

Graph<T> 中的方法参数采用需要 ij 指定顶点,采用一对顶点序号 (i, j) 指定一条边 $\lang V_i, V_j \rang$,$(0 \leq i,j < n)$,$i \neq j$ (不表示自身环);若 $i、j$ 指定的顶点序号超出范围,则抛出序号越界异常。