数据结构：图的定义、存储与遍历应用

当有向图仅一个顶点的入度为 0，其余顶点的入度均为 1，此时是何形状

我们可以看到，这是一棵树结构的图，我们称这种结构为有向树

路径

• 路径：连续的边构成的顶点序列
• 路径长度：路径上边的数目；对于网结构（带权图），是权值之和
• 回路（环）：起点和终点是一个顶点的路径
• 简单路径：除了路径起点和终点可以相同以外，其余顶点均不同的路径
• 简单回路：路径起点和终点可以相同，其余顶点均不同的路径

子图 有两个图：原图 G=(V,E)，子图 G1=(V1,E1)，若满足：V1⊆V、E1⊆E，则称 G1 是 G 的子图

如下，有一个图结构及其部分子图：

联通子图：只要一个子图内部是连通的（即子图中任意两个顶点之间都存在路径），它就可以被称为原图的一个连通子图

联通分量

• 有向图的强连通分量 对于一个有向图的强连通子图，如果它已经包含了所有能相互到达的点和边，无法再加入原图中任何其他顶点而保持强连通性，它就是极大强连通子图；我们也称其为强连通分量

无向图的连通分量 对于一个无向图的连通子图，如果它已经包含了所有能相互到达的点和边，无法再加入原图中任何其他顶点而保持连通性，它就是极大连通子图；我们也称其为连通分量

联通分量和强连通分量的定义很相似，注意有向图的强连通性即可

生成树和生成森林

• 极小连通子图 一个有 n 个顶点图的极小连通子图，它包含图中所有的顶点，但只有足以构成一棵树的 n-1 条边（假设有 n 个顶点）；去掉任意一条边，图就不再连通、加上任意一条边，图就会生成一个环
• 生成树：对于一个连通图，其最小连通子树称为生成树
• 生成森林：对于非连通图，生成森林是由各个连通分量的生成树的集合

在后面，我们会学到网 (带权重的图结构)，其中一个重要的问题就是构造其的最小生成树，以后再来介绍

2. 图的顺序存储结构——邻接矩阵表示法

2.1 各种图结构的邻接矩阵表示

无向图的邻接矩阵

• 建立一个顶点表（记录各个顶点信息），和一个邻接矩阵（表示各个顶点之间的关系）：
  • 设图 A=(V,E) 有 n 个顶点，则有顶点表 Vex[n]，记录每个顶点
  • 图的邻接矩阵是一个二维数组 A.arcs[n][n]，其每个元素的定义为：

A.arcs[i][j] = {
  1, 如果 ⟨i,j⟩∈E 或者 (i,j)∈E
  0, 否则
}

• 邻接矩阵表示了顶点之间的关系，如果两个顶点之间存在边，则数组表示为 1，否则表示为 0

举例 我们有下面这样的一个图结构：

• 我们则能根据顶点之间的关系，创建出邻接矩阵 A.arcs[n][n]

[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]

无向图邻接矩阵的规律

• 对角线元素均为零（因为没有顶点与自己有边关系）
• 无向图的邻接矩阵是对称的（顶点之间的边关系是相对的）
• 通过每一行（每一列）'1'的数量，我们就能确定每一个顶点的度
• 对于一个完全图，对角线元素为 0，其余全部为 1

有向图的邻接矩阵

• 有向图邻接矩阵的建立思路与无向图相同，不同的是在填入 0 或 1 时考虑顶点之间边关系的方向
• 在有向图的邻接矩阵中：第 Vi 行记录了以结点 Vi 为起点的边，第 Vi 列记录了以结点 Vi 为终点的边

举例 有这样的一个有向图：

• 则根据规则，我们能创建如下的邻接矩阵

[0 1 1 0]
[0 0 0 0]
[0 0 0 1]
[1 0 0 0]

有向图邻接矩阵的规律

• 对角线元素均为零（因为没有顶点与自己有边关系）
• 矩阵可能不是对称的（边关系是有向的）
• 通过每一行的'1'的数量，我们能确认顶点 Vi 的出度；通过每一列的'1'的数量，我们能确认顶点 Vi 的入度；出度和入度之和就是顶点的度

网的邻接矩阵 与有向图类似，但是对于矩阵中填入的数据，我们填入的就不是 0 或 1 了，而是边所带有的权值

• 邻接矩阵 A.arcs[i][j] 的定义：

A.arcs[i][j] = {
  Wij, 如果 ⟨i,j⟩∈E 或者 (i,j)∈E
  ∞, 否则
}

• 这里我们使用无限（∞）来表示两个顶点之间没有边关系，方便后面的算法进行运算

举例 有这样的一个网结构：

我们根据定义能获得它的邻接矩阵：

[∞ 5 7 ∞ ∞]
[∞ 4 ∞ ∞ ∞]
[8 ∞ ∞ ∞ 9]
[∞ ∞ 5 ∞ 6]
[∞ ∞ 5 ∞ ∞]
[3 ∞ ∞ 1 ∞]

2.2 图 (网) 邻接矩阵的类型定义

• 我们使用两个数组来分别存储顶点表和邻接矩阵。

#define MaxInt 10000 // 表示极大值，用于网结构中权值的赋值
#define MVNum 100; // 设置最大顶点数
typedef char VerTexType; // 设顶点的数据类型为字符型
typedef int ArcType; // 假设边的权值类型为整形
typedef struct {
    VerTexType vexs[MVNum]; // 顶点表
    ArcType arcs[MVNum][MVNum]; // 邻接矩阵
    int vexnum, arcnum; // 图的当前点数和边数
} AMGraph;

• 这就是图的邻接矩阵初始化后的结构，对于不同形式的网结构（有向、无向；带权、不带权）分别进行特别的处理，将网中的数据填入
• 接下来以无向网为例，介绍的邻接矩阵的建立

2.3 无向网的邻接矩阵的建立

算法思想

• 先确定总顶点数和总边数
• 依次输入点的信息存入顶点表中
• 初始化邻接矩阵，使每个权值初始化为极大值
• 根据权值来构造邻接矩阵

代码实现

Status CreateUDN(AMGraph &G){
    cin >> G.vexnum >> G.arcnum; // 输入总顶点数和总边数
    for(i = 0; i < G.vexnum; ++i){ // 依次出入顶点的信息
        cin >> G.vex[i];
    }
    for(i = 0; i < G.vexnum; ++i){
        for(j = 0; j < G.vexnum; ++j){
            G.arcs[i][j] = MaxInt; // 初始化矩阵，将边关系的值设置为无限大
        }
    }
    for(k = 0; k < G.arcnum; ++k){
        cin >> v1 >> v2 >> w; // 输入一条边所依附的顶点以及其权值
        i = LocateVex(G, v1);
        j = LocateVex(G, v2); // 确定 v1、v2 在 G 中的位置
        G.arcs[i][j] = w; // 将权值重置为 w
        G.arcs[j][i] = G.arcs[i][j]; // 无向网两顶点之间的权值相等
    }
    return OK;
}

• 在这里函数 LocateVex 是图的顶点查找算法，根据顶点的值来查找顶点的位置，具体实现如下：

int LocateVex(AmGraph G, VertexType u){
    int i;
    for(i = 0; i < G.vexnum; ++i){
        if(u == G.vex[i]) return i; // 若顶点值相同，返回位置
    }
    return -1; // 否则，返回 -1
}

其他图结构的实现

• 无向图，就是不带有权值的网结构；在初始化时，我们将每一个权值初始为 0，在构造邻接矩阵时，如果两个顶点之间有边关系，我们再将权值重置为 1
• 有向图，它的邻接矩阵是非对称矩阵，我们仅为 G.arcs[i][j] 赋值，不用给 G.arcs[j][i] 赋值
• 有向图，结合了上面两个结构的特点，初始时权值为 0，也只需要给边关系赋值为 1 一次

2.4 邻接矩阵的优缺点

优点

• 直观、简单、好理解
• 方便检查任意一对顶点之间是否存在边
• 方便找任一顶点的所有邻接点
• 方便计算任一顶点的度（从该顶点发出的边数为出度，指向该顶点的边数为入度），对于无向图：对应行（或列）非零元素的个数；对于有向图：对应行非零元素的个数是出度，对应列非零元素的个数是入度，顶点的度为二者相加。

如图，对下面这个邻接矩阵，我们可以得出以下信息：

[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]

• 这是一个无向图，有五个顶点
• 每个顶点之间的连接关系
• 每个顶点的度

得到如下的无向图：

缺点

• 如果要对图的元素进行增删，就要更改矩阵的结构，十分不便
• 存在稀疏图时（顶点很多，但是边很少），有大量无效元素，浪费空间
• 统计图中的边数时，要遍历完矩阵中所有的元素，浪费大量时间

3. 图的链式存储结构——邻接表表示法

3.1 各种图结构的邻接表表示

无向图的邻接表

• 我们将图中所有顶点的信息按照顺序存入一个一维数组中，数组中每个元素都是一个链表，每个顶点在数组中的位置由其顶点序号决定
• 数组中的每个元素对应一个链表的头结点，表示以该顶点为起点的所有边
• 头结点除了可以存储顶点本身的信息（如顶点数据、标志位等），还包含一个指针，指向该顶点的一个邻接点
• 链表中的后续节点，称为表结点，表示一个邻接点，通常包含以下几个信息：
  • 邻接顶点的序号
  • 指向下一个邻接点节点的指针
  • 和边相关的信息（权重等）

举例 有如下的图结构：

用邻接表来进行存储，如下所示：

无向图邻接表的特点

• 邻接表并不唯一，每个顶点的邻接点没有特别的顺序
• 若无向图中有 n 个顶点、e 条边，则邻接表需要 n 个头结点和 2e 个表结点，适用于存储稀疏图
• 无向图中顶点 Vi 的度为第 i 个单链表中的表结点数

有向图的邻接表

• 对于有向图邻接表，每个单链表只存储该结点的出度指向的顶点

举例 有如下一个有向图：

我们能得到这样的一个邻接表：

有向图邻接表的特点

• 顶点 Vi 的出度为第 i 个单链表中的结点个数
• 顶点 Vi 的入度为整个单链表中邻接点域值是 i-1 的结点个数
• 所以，要找到一个顶点的出度简单，而找到入度繁琐

逆邻接表 为了解决找入度难的问题，我们设计出了逆邻接表。

对于上图的有向图结构，我们有这样的逆邻接表：

• 特点：
  • 顶点 vi 的入度为第 i 个单链表中的结点个数
  • 顶点 vi 的出度为整个单链表中邻接点域值是 i-1 的结点个数
  • 找到一个顶点的入度简单，而找到出度繁琐

3.2 图 (网) 邻接表的类型定义

头结点的类型定义

• 邻接表的实现，在于两个关键点——一个是数组的结构定义和单链表结构的定义
• 邻接表的数组是由多个单链表的头结点构成的，于是我们有如下的结构定义：

typedef struct VNode{
    VerTexType data; // 存储的结点信息
    ArcNode* firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNmu];

• 在这里 AdjList 表示的是邻接表的类型，我们在申明一个邻接表时，可以使用 AdjList v，相当于 VNode v[MVNum]

表结点的类型定义

typedef struct ArcNode{
    int adjvex; // 该边所指向的顶点的位置
    struct ArcNode* nextarc; // 指向下一条边的指针
    OtherInfo info; // 和边有关的信息
} ArcNode;

图的类型定义

typedef struct{
    AdjList vertices; // 邻接表的数组
    int vexnum, arcnum; // 图中的顶点数和边数
} ALGraph;

3.3 无向图邻接表的建立

算法思想

1. 输入总顶点数和总边数
2. 建立顶点表：
   1. 依次输入顶点的信息，存入顶点表中
   2. 是每个表头结点的指针域初始化为 null
3. 创建邻接表：
   1. 依次输入每条边依附的两个顶点
   2. 确定两个顶点的序号 i 和 j，建立边结点
   3. 将此边结点分别插入到 vi 和 vj 对应的两个边链表的头部

代码实现

Status CreateUDG(ALGraph &G){
    cin >> G.vexnum >> G.arcnum; // 输入图的顶点数和边数
    for(int i = 0; i < G.vexnum; ++i){
        cin >> G.vertices[i].data; // 输入个头结点的值
        G.vertices[i].firstarc = NULL; // 将头结点的指针域置为空
    }
    for(int k = 0; k < G.arcnum; ++k){
        cin >> v1 >> v2; // 驶入一条边依附的两个顶点
        int i = LocateVex(G, v1); // 寻找顶点的位置
        int j = LocateVex(G, v2);
        p1 = new ArcNode; // 生成一个新的边结点 p1
        p1->adjvex = j; // 邻接点的序号为 j
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1; // 将新结点 p1 插入顶点 vi 的边表头部
        p2 = new ArcNode; // 生成一个对称新的边结点 p2
        p2->adjvex = i; // 邻接点的序号为 i
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2; // 将新结点 p2 插入顶点 vj 的边表头部
    }
    return OK;
}

3.4 邻接表的优缺点

优点

• 方便找到任一顶点的所有邻接点。
• 节约稀疏图的空间：需要 N 个头指针和 2E 个结点（每个结点至少两个指针域）
• 对于无向图，方便计算计算任一结点的度

缺点

• 对于有向图，只能计算出度；需要构造逆邻接表才能方便计算入度
• 不方便检查任意两个顶点之间是否有边关系

4. 邻接矩阵和邻接表的关系

1. 联系：邻接表中每个链表对应邻接矩阵中的每一行，链表中结点个数等与矩阵中每一行非零元素的个数
2. 区别：
   1. 对于任意确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表并不唯一（连接次序与顶点编号无关）
   2. 邻接矩阵的空间复杂度为 O(n^2)，而邻接表的空间复杂度为 O(n+e)
3. 用途：邻接矩阵多用于稠密图，而邻接表多用于稀疏图

5. 有向图的链式存储结构——十字链表

5.1 十字链表的表示

• 有向图中，若使用邻接表，只便于查找出边；使用逆邻接表，只便于查找入边
• 十字链表 (Orthogonal List) 是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表
• 十字链表的存储结构，使每个结点能同时存储出入边信息，提高图结构的访问效率

链表中包含两种结点类型，顶点结点和弧结点

顶点结点，每个顶点信息包含：

• 数据域 data：存储顶点本身的数据；
• 指针域：
  • firstin：指向以该顶点为终点的第一条入边。
  • firstout：指向以该顶点为起点的第一条出边。

弧结点，每条边同时连接两个顶点，并串入这两个顶点的出链表与入链表，包含：

• 数据域：
  • tailvex：该边的起点编号
  • headvex：该边的终点编号
• 指针域：
  • tlink：指向与该边起点相同的下一条出边
  • hlink：指向与该边终点相同的下一条入边

5.2 十字链表的类型定义

• 头结点：

typedef struct VNode {
    char data; // 顶点数据
    ArcBox* firstIn; // 指向以该顶点为终点的第一条边（入边）
    ArcBox* firstOut; // 指向以该顶点为起点的第一条边（出边）
} VNode;

• 边结点：

typedef struct ArcBox {
    int tailVex; // 边的起点（尾）
    int headVex; // 边的终点（头）
    ArcBox* hLink; // 指向终点相同的下一条边（入边链）
    ArcBox* tLink; // 指向起点相同的下一条边（出边链）
    // 可扩展：边权值、标签等信息
} ArcBox;

举例 有这样的一个有向图：

我们根据十字链表的定义，可以得到如下的存储结构示意图：

可以看到：一个头顶点，顺着两个不同方向的链表，我们能很简单的计算出其出度和入度

6. 无向图的链式存储结构——多重链表

6.1 多重链表的表示

• 多重链表的设计思路就是一个边关系只使用一个结点来表示，多个顶点来共享一个边结点

邻接多重表的结构和十字链表类似，包含顶点结点和弧结点两种结点类型

顶点结点，每个头结点包括：

• 数据域data：存储顶点的数据
• 指针域：
  • firstEdge：指向该顶点的第一条边的指针（即边结点）

弧结点，每条边只创建一个结点，供其两个顶点共享，结构包括：

• 指针域：
  • ivex：该边关联的一个顶点编号
  • jvex：该边关联的另一个顶点编号
  • ilink：指向下一条以 ivex 为端点的边
  • jlink：指向下一条以 jvex 为端点的边
• 信息域：
  • info：存储边的信息，如权重
• 标志域mark：标记这个结点是否被搜索过

6.2 多重链表的类型定义

• 头结点：

typedef struct VNode {
    char data; // 顶点数据
    EdgeNode* firstEdge; // 指向第一条边
} VNode;

• 边结点：

typedef struct EdgeNode {
    int ivex, jvex; // 边连接的两个顶点
    struct EdgeNode* ilink; // 指向与 ivex 相连的下一条边
    struct EdgeNode* jlink; // 指向与 jvex 相连的下一条边
    int weight; // 可选：边的权值
} EdgeNode;

举例 有这样一个无向图，如下：

我们根据多重链表的定义，构建如下的多重链表：

• 与之前的普通邻接表相比，边结点大大减少了，实现了边关系的简化

二、图的遍历

• 从已给的连通图中某一项出发，沿着一些边遍历图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，这也是图的基本运算
• 图中顶点元素之间的关系情况多样，有可能存在回路，再访问某个顶点后有可能回到之前访问过的结点，怎么样避免重复访问呢？
• 解决思路：设置辅助数组 visited[i]，用来记录每个结点的访问情况：
  • 初始状态 visited[i] 为 0
  • 顶点 i 被访问后，改为 1，防止被多次访问
• 图常用的遍历方式有两种：深度优先遍历（DFS）和广度优先遍历（BFS）

本节我们来介绍这两种遍历算法

1. 图的深度遍历

1.1 深度遍历算法思想

图的深度优先遍历是一种类似于树的先序遍历的图遍历算法，其核心思想是：从某个顶点出发，尽可能'深'地搜索图中的顶点，直到无法继续，再回溯继续搜索未访问的顶点

算法思路

1. 从起始顶点开始访问
2. 访问当前顶点后，标记为'已访问'
3. 递归访问当前顶点的未访问邻接点
4. 若某路径无可访问邻点，则回溯到上一个顶点继续尝试
5. 直到所有顶点都被访问后，才结束遍历

例：有如下这样一个图结构，求其深度遍历次序

解：根据算法设计，我们得到遍历顺序为： 1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7 或 1 -> 2 -> 5 -> 8 -> 4 -> 3 -> 6 -> 7 或…

1.2 深度遍历实现

• 之前我们学过树的遍历操作，了解其基于递归实现的本质。
• 图由于具有相似的结构，同样可以使用遍历的思想来进行图的深度遍历。
• 图存储结构的实现有邻接矩阵和邻接表两种实现方式，下面我们来分别介绍。

邻接矩阵实现

算法步骤

我们以顶点 0 为起点，对该图进行深度优先遍历（DFS），核心步骤如下：

1. 将当前顶点标记为已访问。
2. 访问当前顶点。
3. 遍历邻接矩阵中当前顶点对应的那一行所有顶点。
4. 若某个顶点与当前顶点有邻接关系且未被访问，则递归调用 DFS 访问该顶点。

举例 例： 有如下的一个无向图和其邻接矩阵：

[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]

算法流程：

• 对顶点 1 调用 DFS
  • 标记并访问顶点 1；
  • 遍历邻接矩阵第 1 行，发现顶点 2 为邻接点，递归调用 DFS(2)
• 对顶点 2 调用 DFS
  • 标记并访问顶点 2；
  • 遍历第 2 行，发现顶点 3 为未访问的邻接点，递归调用 DFS(3)
• 对顶点 3 调用 DFS
  • 标记并访问顶点 3；
  • 遍历第 3 行，发现顶点 4 为未访问的邻接点，递归调用 DFS(4)
• 对顶点 4 调用 DFS
  • 标记并访问顶点 4；
  • 遍历第 4 行，没有未访问的邻接点，返回上一层
• 返回顶点 3，继续遍历第 3 行
  • 发现顶点 5 为未访问的邻接点，递归调用 DFS(5)
• 对顶点 5 调用 DFS
  • 标记并访问顶点 5；
  • 遍历第 5 行，没有未访问的邻接点
• 所有递归返回，DFS 过程结束

遍历顺序： 1 -> 2 -> 3 -> 4 -> 5

我们能看到，由于邻接矩阵的唯一性，使用邻接矩阵进行深度遍历的结果也是唯一的

代码实现

void DFS(AMGraph G, int v){
    cout << v;
    visited[v] = true; // 从第 i 个顶点访问
    for(int w = 0; w < G.vexnum; w++){ // 依次检查 v 所在的行
        if((G.arcs[v][w] != 0) && (!visited[w])){ // w 是 v 的邻接矩阵，如果 w 未被访问，就对其递归调用 DFS
            DFS(G, w);
        }
    }
}

邻接表实现

算法步骤 我们将数组中第一个头结点（顶点结点）作为起点，进行深度遍历：

1. 将当前顶点标记为已访问
2. 访问当前顶点
3. 遍历当前顶点的单链表中的边节点（即邻接点）
4. 若某个邻接点未被访问，则递归调用 DFS 访问该邻接点

代码实现

void DFS(ALGraph G, int v) {
    // 访问当前顶点，输出顶点信息
    cout << G.vertices[v].data;
    // 标记当前顶点为已访问
    visited[v] = true;
    // 获取当前顶点的第一个邻接点
    ArcNode *p = G.vertices[v].firstarc;
    // 遍历当前顶点的所有邻接点
    while (p != NULL) {
        // 如果邻接点未被访问，则递归调用 DFS 访问它
        if (!visited[p->adjvex]) DFS(G, p->adjvex);
        // 访问下一个邻接点
        p = p->nextarc;
    }
}

1.3 算法效率分析

• 用邻接矩阵来遍历，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为 O(n^2)
• 用邻接表来表遍历，虽然有 2e 个表结点，但只需要扫描 e 个结点即可完成遍历，加上访问 n 个头结点的时间，时间复杂度为 O(n+e)

2. 图的广度遍历

2.1 广度遍历算法思想

图的广度优先遍历是一种类似于树的层次遍历的图遍历算法，其核心思想是： 从某个起始顶点出发，首先访问其所有邻接点，然后再依次访问这些邻接点的邻接点，直到所有顶点都被访问为止

算法思路

1. 从起始顶点开始访问，并标记为'已访问'
2. 依次访问该顶点的所有未被访问的邻接点，并标记
3. 再依次访问这些邻接点的所有未被访问的邻接点
4. 按照'先访问过的顶点，其邻接点优先'的顺序，逐层向外扩展
5. 直到图中所有可达的顶点都被访问为止，遍历结束

例：有如下这样一个图结构，求广度遍历次序

解：根据算法，我们得到遍历顺序为： 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 或 1 -> 3 -> 6 -> 7 -> 2 -> 4-> 5 -> 8 或…

2.2 广度遍历实现

广度优先遍历（BFS）的核心思想是：按层次、一圈一圈地访问图中的顶点 先访问的顶点，其邻接点也应该先被访问，后访问的顶点则推迟处理——这就需要一个先进先出的结构来管理顶点的访问顺序，队列完美满足这个需求

邻接矩阵实现

算法步骤 以图的邻接矩阵为基础，从顶点 v 出发执行广度遍历：

1. 访问并标记顶点 v
2. 将 v 入队
3. 当队列非空：
   • 出队一个顶点 u
   • 遍历邻接矩阵中 u 所在行，找到所有未访问邻接点 w
   • 将所有满足条件的 w 标记并入队

举例 例： 有如下的一个无向图和其邻接矩阵：

[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]

算法流程：

1. 访问并入队顶点 1
2. 出队 1，发现邻接点 2 和 4，访问并入队
3. 出队 2，发现邻接点 3 和 5，访问并入队
4. 出队 4，无新邻接点
5. 出队 3，无新邻接点
6. 出队 5，无新邻接点

最终遍历顺序： 1 -> 2 -> 4 -> 3 -> 5

代码实现

void BFS(AMGraph G, int v) {
    cout << v; // 访问第 v 个顶点
    visited[v] = true;
    InitQueue(Q); // 初始化队列
    EnQueue(Q, v); // 起始顶点入队
    while (!QueueEmpty(Q)) {
        DeQueue(Q, u); // 出队一个顶点 u
        for (int w = 0; w < G.vexnum; w++) {
            if (G.arcs[u][w] != 0 && !visited[w]) { // 若 u 和 w 相邻且 w 未访问
                cout << w; // 访问 w
                visited[w] = true;
                EnQueue(Q, w); // w 入队，后续访问其邻接点
            }
        }
    }
}

邻接表实现

算法步骤 从某个起始顶点 v 出发，进行如下操作：

1. 访问并标记 v
2. 入队
3. 当队列非空时：
   • 出队一个顶点 u
   • 遍历 u 对应的邻接链表中的每一个元素
   • 若邻接链表元素 w 未访问，则访问、标记并入队

代码实现

void BFS(ALGraph G, int v){
    cout << v; // 访问第 v 个顶点
    visited[v] = true;
    InitQueue(Q); // 初始化队列
    EnQueue(Q, v); // 起始顶点入队
    while(!QueueEmpty(Q)){
        DeQueue(Q, u); // 出队一个顶点 u
        // 访问顶点的邻接链表
        for(int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)){
            if(!visited[w]){ // 访问 w
                cout << w;
                visited[w] = true;
                EnQueue(Q, w); // w 入队，后续访问其邻接点
            }
        }
    }
}

• FirstAdjVex(G, u)：返回图 G 中顶点 u 的第一个邻接点（若没有邻接点则返回 -1）

int FirstAdjVex(ALGraph G, int u) {
    if (G.vertices[u].firstarc != NULL) return G.vertices[u].firstarc->adjvex; // 返回第一个邻接点编号
    else return -1;
}

• NextAdjVex(G, u, w)：在顶点 u 的邻接点中，找到继 w 之后的下一个邻接点（若没有则返回 -1）

int NextAdjVex(ALGraph G, int u, int w) {
    ArcNode *p = G.vertices[u].firstarc;
    while (p != NULL) {
        if (p->adjvex == w && p->nextarc != NULL) return p->nextarc->adjvex; // 返回 w 的下一个邻接点编号
        p = p->nextarc;
    }
    return -1;
}

2.3 算法效率分析

和深度遍历一致：

• 用邻接矩阵来遍历，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为 O(n^2)
• 用邻接表来表遍历，虽然有 2e 个表结点，但只需要扫描 e 个结点即可完成遍历，加上访问 n 个头结点的时间，时间复杂度为 O(n+e)

3. 非连通图的遍历

在图的遍历中，如果图是非连通图（即图中存在多个不连通的子图或称连通分量），单次遍历不能遍历所有顶点；因此，我们需要对每一个未被访问的顶点都启动一次新的遍历

拿这样一个非连通图来举例：

它的邻接矩阵为：

[0 1 1 0 0]
[1 0 1 0 0]
[1 1 0 0 0]
[0 0 0 0 1]
[0 0 0 1 0]

• 使用一般的深度遍历后，并不能遍历到 4 号顶点和 5 号顶点；为此，我们要将每一个顶点都作为新起点，重启一次遍历

for (int i = 0; i < G.vexnum; i++) {
    if (!visited[i]) {
        DFS(i); // 从该未访问顶点开始一个新的 DFS
    }
}
for (int i = 0; i < G.vexnum; i++) {
    if (!visited[i]) {
        BFS(i); // 从该未访问顶点开始一个新的 BFS
    }
}

三、图的应用

1. 图的生成树

生成树作为图的一个核心概念，广泛应用于网络连接、路径规划和最小代价设计等场景；本节我们学习图的生成树的性质与构造方法

1.1 图生成树的概念

前面我们介绍过图的生成树，即——对于一个无向连通图G=(V,E)，其生成树是包含图中所有顶点的一个极小连通子图

如下所示的图结构：

则它的几个生成树结构为：

• 一个图可以具有多个不同的生成树
• 所有生成树具有以下特性：
  • 生成树顶点个数与图的顶点个数相同
  • 生成树是图的极小连通子图，去掉任意一条边就非连通；加上任意一条边就必然形成回路
  • 一个有 n 个顶点的连通图的生成树有 n-1 条边
  • 生成树中任意两个顶点间的路径是唯一的

下面我们学习图生成树的构造

1.2 图生成树的构造算法

算法思路

• 设图 G=(V,E) 是个连通图，当从图任一顶点出发遍历图 G 时，将边集 E(G) 分成两个集合 T(G) 和 B(G)
• 其中，T(G) 是遍历图时所经过的边的集合，B(G) 是遍历图时未经过的边的集合
• 显然，G1(V,T) 是图 G 的极小连通子图，即子图 G1 是连通图 G 的生成树
• 根据遍历方法（深度遍历和广度遍历）的不同，也就会构造出不同的生成树

示例 有这样的一个无向图结构：

根据遍历方式的不同，我们能得到不同的最小生成树，如下图：

代码实现 我们以邻接表+DFS 算法为例：

void DFS_GenTree(ALGraph G, int v) {
    visited[v] = true;
    ArcNode *p = G.vertices[v].firstarc; // 从指定起始顶点开始遍历
    while (p != NULL) {
        int w = p->adjvex; // w 是 v 的第一个邻接点
        if (!visited[w]) { // 输出生成树的边 (v, w)
            cout << "(" << G.vertices[v].data << "," << G.vertices[w].data << ")" << endl;
            DFS_GenTree(G, w); // 继续向下递归
        }
        p = p->nextarc; // 移动到下一个顶点
    }
}

2. 图的最小生成树

在图论中，生成树是连接图中所有顶点的无环子图；对于一个带权无向图（即网），可能存在多棵生成树，而其中边权总和最小的生成树称为最小生成树（Minimum Spanning Tree, MST），也叫最小代价树

最小生成树的应用：

• 城市管道铺设设计，如何用最少的管道连接所有点
• 通信信号塔搭建，降低总成本的网络连接方案
• 电网线路布局等工程问题

构造最小生成树是解决这类实际问题的关键第一步，下面我们来介绍最小生成树的构造

2.1 最小生成树的构造原理——MST 性质

构造最小生成树的算法有很多，但大多数都使用了 MST(Minumum Spanning Tree) 性质——设 N=(V,E) 是一个连通网，U 是顶点集 V 的一个非空子集；若 (u,v) 是一条就有最小权值的边，其中 u∈U,v∈V-U，则必然存在一棵包含边 (u,v) 的最小生成树

MST 性质解释：

• 在生成树的构造过程中，图中 n 个顶点分属于两个集合：
  • 已经落在生成树上的顶点集：U
  • 尚未落在生成树上的顶点集：V-U
• 接下来，应在所有连通顶点集 U 和未连通顶点集中的顶点选取权值最小的边

下面介绍两个实现了 MST 性质最小生成树的构造算法——Prim 算法和 Kruskal 算法

2.2 最小生成树构造算法

Prim 算法

算法思想

• 设 N = (V,E) 是一个连通网，TE 是 N 上最小生成树中边的集合
• 初始令 U={u0}, (u0∈V), TE = {}
• 在所有 u∈U，v∈V-U 的边 (u,v)∈E 中，找一条代价最小（权值最小）的边 (u0,v0)
• 将顶点 v0 并入 U，(u0,v0) 并入集合 TE
• 重复以上操作，直到 U=V 为止，则 T=(V,TE) 为 N 的最小生成树

举例 如下图，有一个连通网结构：

构造过程：

Kruskal 算法

算法思想

• 设连通网 N=(V,E)，令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T=(V,{})，每个顶点自成一个连通分量
• 在 E 中选取代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上（不会形成环路），则将此边加入到 TE 中；否则，舍去此边，选取下一条代价最小的边
• 以此类推，直到 T 中所有顶点都在同一连通分量上为止

举例 如下图，有一个连通网结构：

构造过程：

1. 我们构造出非连通图 T，T 中包含 N 的所有顶点，即 V={1，2，3，4，5，6}
2. 我们依次选取权值最小的边来构造最小生成树：
   1. 选取 (1,3) 加入 TE，TE={(1,3)}
   2. 选取 (4,6) 加入 TE，TE={(1,3)、(4,6)}
   3. 选取 (2,5) 加入 TE，TE={(1,3)、(4,6)、（2,5）}
   4. 选取 (3,6) 加入 TE，TE={(1,3)、(4,6)、（2,5）、（3,6）}
   5. 选择 (3,4)、(1,4)，但形成回路，舍去
   6. 选取 (2,3) 加入 TE，TE={(1,3)、(4,6)、（2,5）、（3,6）、(2,3)}
   7. 其余边依次考虑，但都会形成环路，舍去
   8. 遍历完所有边后，构造结束，生成最小生成树为 T=(V,TE)

两种算法比较

3. 图的最短路径问题

在日常生活中，我们驾车或者出行时，都会有交通路线选择的问题——甲地到乙地有多条路径，选择哪一条路最短？ 于是我们引出了最短路径的概念，通过将路线问题抽象为有向带权图，我们就能借助图算法来系统地解决路径选择难题

3.1 两种最短路径问题

常见最短路径问题 我们能把现实路径问题抽象成以下数学模型：

• 交通网络使用有向图来表示；
• 地点使用顶点表示；
• 两个地点之间的路线用弧表示；
• 两地之间的距离、花费、所需时间用弧上的权值表示

最短路径主要有两类问题：

两点之间最短路径 有如下的网结构：

求从 v1 到 v7 的路径及路径长度：

从某点到其他各点的最短路径 有如下的网结构：

从 v0 点到其他各点的最短路径为：

最短路径算法

• 从单一源点到所有其他顶点的最短路径的问题（单源问题），采用Dijkstra算法
• 求所有顶点间的最短路径的问题，采用Floyd算法

下面来介绍这两种算法

3.2 Dijkstra 算法

Dijkstra 算法通过贪心策略逐步扩展最短路径，最终求出从源点 v0 到所有顶点的最短路径

算法思路

• 初始化两个集合：
  • SSS：已确定最短路径的顶点集合，初始为 v0；
  • TTT：待确定的顶点集合，为其余所有顶点
• 使用数组 D[i] 记录当前从 v0 到 vi 的最短路径长度。初值为：
  • 若 <v0,vi> 存在，则为其权值；
  • 否则为 ∞
• 每次从 TTT 中选取使 D[i] 最小的顶点 vj 加入 SSS；
• 用 vj 作为中间点，更新其他未确定点的最短距离；
• 重复直到所有顶点加入 SSS，即全部路径确定

举例 有如下的网结构，求从 V0 到其他各顶点的最短路径：

算法步骤如下：

1. 初始时，辅助数组 DDD：

2. 执行第二次后的最短路径更新为：

3. 重复执行几次后，直到所有顶点都加入 S 集合后，我们得到如下表格，即单源顶点的最短路径表：

3.3 Floyd 算法

• 对于一个有向图，我们可以重复执行 n 次 Dijkstra 算法，来遍历获得所有顶点间的最短路径，但是较为繁琐
• 我们可以采用Floyd算法，来更简便地求出所有顶点间的最短距离

算法思路

1. 初始时，我们设置一个 n 阶方阵，令其对角线元素为 0，若存在弧<Vi,Vj>，则对应元素为其权值；否则为无穷大（∞）
2. 接着逐步在原有的直接路径上增加中间顶点，若加入中间顶点后路径变短，则修改路径长度，否则维持原值；所有顶点试探完毕后，算法结束

举例 有如下的图结构，求每个点到其余各点的最短路径：

算法步骤如下：

• 初始的路径矩阵为：

[A A A]
[B B B]
[C C C]

其值为：

[0 4 11]
[6 0 2]
[3 ∞ 0]

• 我们尝试将中间节点加入之前的原路径，如果存在更小的路径，就将路径矩阵中的值进行替换

如：

1. 加入 A 顶点后，路径矩阵为

[A A A]
[B B B]
[C A C]

其值为：

[0 4 11]
[6 0 2]
[3 ∞→7 0]

2. 加入 B 顶点后，路径矩阵为：

[A A A]
[B B B]
[C A C]

其值为：

[0 4 11→6]
[6 0 2]
[3 7 0]

3. 加入 C 顶点后，路径矩阵为：

[A A A]
[B B B]
[C A C]

其值为：

[0 4 6]
[6→5 0 2]
[3 7 0]

3. 所有顶点都试探性加入后，算法结束，得到最终的最短路径矩阵

[0 4 6]
[5 0 2]
[3 7 0]

4. 图的其他应用

4.1 有向无环图相关概念

有向无环图（DAG）是一种有向图，但其中不存在从某个顶点出发沿有向边能回到自身的路径（即不包含环路） 通俗理解：图中所有边都有方向，且沿着方向走不会形成闭环

有向无环图的特性

• 有向性：边具有方向（例如从 A 指向 B）
• 无环性：不存在形如 A → B → C → A 的路径
• 可以进行拓扑排序：DAG 是可以进行拓扑排序的图（这是一种线性排序，使得所有边 u → v 中，u 都出现在 v 之前）

由于其特性，我们常常使用它来描述一个工程或者系统的进行过程，一个工程可以分为若干个子工程，只要完成了子工程，就可以导致整个工程的完成

4.2 工程网络

AOV 网 用一个有向图来表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网（Activity On Vertex network）

AOE 网 用一个有向图来表示一个工程的各子工程及其相互制约的关系，其中以弧表示活动，顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称AOE网（Activity On Edge network）

AOV 网被用于拓扑排序，而 AOE 网被用于关键路径，下面来分别介绍两种网络

4.3 拓扑排序

AOV 网的特点

• 若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继
• 若<i,j>是网中有向边，则 i 是 j 的直接前驱，j 是 i 的直接后继
• AOV 网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，这显然不成立

如何判断 AOV 网中是否有回路呢？ 我们可以使用拓扑序来解决这个问题

拓扑排序的概念 在 AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧<i,j>存在，则在这个序列中，i 一定在 j 前面，具有这种性质的线性序列叫做拓扑有序序列，相应的拓扑有序排列算法叫做拓扑排序

拓扑排序思路

1. 在有向无环图中选一个没有前驱的顶点并且输出
2. 将该顶点和它的出度边删除，再从剩余顶点中选择没有前驱的顶点并输出
3. 重复执行上面两步，直到不存在没有前驱的结点为止

有如下的一个有向无环图结构：

算法实现步骤：

1. 网结构中，没有前驱的顶点有 1 和 9，我们选择 1 作为开头；将 1 加入序列，并删除顶点 1 和它的出度边
2. 目前，网结构中没有前驱的顶点有 2、4、12、9；我们选择 2，加入序列，并删除顶点 2 和它的出度边
3. 重复执行上述两步，最终我们可以得到一个这样的序列：1、2、3、4、5、7、9、10、11、6、8、12

需要注意的是：拓扑序列并不是唯一的，取决于网结构和选取顶点的顺序，但是所有的拓扑序列中，一个顶点的前驱一定出现在该顶点之前

拓扑排序的应用 回到之前的问题：如何判断 AOV 网中是否有回路呢？

通过拓扑排序算法，我们可以看到：

• 若有向图中存在环形结构，则在拓扑排序算法中，它一定存在无法被删除的前驱，则一定不能加入拓扑序列中

所以，对于一个有向图，若其所有顶点都在拓扑有序序列中，则该 AOV 网中必定不存在环，也就是有向无环图

如上图所示，对于这样一个网结构的拓扑有序序列中，必然不会出现 3、5、8 这三个顶点

4.4 关键路径

• 在 AOE 网结构中，我们用弧表示活动，用顶点表示事件，弧的权值表示活动持续时间
• 顶点的事件表示在它之前活动已经完成，在它之后活动可以开始

例如：有如下的活动表：

我们可以得到如下的 AOE 网：

关键路径的相关概念 对于 AOE 网，我们主要关心两个问题：

1. 完成整项工程需要多长时间？
2. 哪些活动是影响工程进度的关键？

由此，我们引出了两个关键概念：

• 路径长度——路径上各活动持续时间之和
• 关键路径——路径长度最长的路径

关键路径的描述量 为了确定关键路径，我们需要定义几个描述量：

• 对于每个顶点（事件），有：
  1. ve(vj)——表示事件 vj 的最早发生时间
  2. vl(vj)——表示事件 vj 的最迟发生时间
• 对于每个边（活动），有：
  1. e(i)——表示活动 ai 的最早开始时间
  2. l(i)——表示活动 ai 的最迟开始时间
  3. 时间余量：l(i)-e(i) 表示活动 ai 的时间余量

对于时间余量为零的活动，即 l(i)-e(i)==0 的活动，我们称其为关键路径上的活动，也就是关键活动，由多个关键活动组成的路径，就是关键路径。

怎么找寻关键活动呢？

关键路径的计算

如上图所示：我们设活动 ai 用<j,k>表示，其持续时间记为 wj,k，则有：

{
  e(i) = ve(j)
  l(i) = vl(k) - wj,k
}

可以看到，关键路径的计算的关键在于计算事件最早发生事件和最迟发生事件 如何求出 ve(j) 和 vl(k)——即某事件最早发生时间和最晚发生时间呢？

某事件最早发生时间

• 一个事件是多个前驱事件（活动）完成后的'汇合点'，它的最早发生时间，必须等待所有前驱活动都完成
• 从 Ve(起点)=0 开始向前推进，对图中所有活动 <j, k>，持续时间为 wj,k 有：

ve(k) = max_{j ∈ pred(k)} [ve(j) + wj,k]

即：某事件 k 的最早发生时间 = 所有前驱事件 j 的最早发生时间 + 活动 <j, k> 的耗时的最大值

某事件最迟发生时间

• 一个事件最晚能发生的时间，需要保证不会耽误整个项目进度；也就是说，从该事件出发的所有后续活动，最早要开始的那一个，决定该事件最晚何时能发生，否则就会"误工"
• 从 Vl(终点)=Ve(终点) 开始向后推进，对图中所有活动 <j, k>，持续时间为 wj,k 有：

vl(j) = min_{k ∈ succ(j)} [vl(k) - wj,k]

即：某事件 j 的最迟开始时间 = 所有后继事件 k 的最迟开始时间 - 活动 <j, k> 的耗时的最小值

举例 如下图的 AOE 网结构，求它的：

1. ve(i)、vl(j)；
2. e(i)、l(i)、l(i)-e(i)

关键活动

计算步骤：

1. 我们根据公式可以求出 ve(i) 和 vl(i),结果如下表：

2. 我们获取了 ve(i) 和 vl(i)，就能计算出 e(i)、l(i) 和 l(i)-e(i)

3. 由表可知，关键活动为：a1、a4、a7、a8、a10、a11

关键路径总结

1. 若网中有几条关键路径，则需要加快同时在关键路径上的关键活动
2. 如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短整个工程完成的时间
3. 处于所有关键路径上的活动完成时间不能缩短太多，否则会使原来的关键路径变成非关键路径；这是就需要重新寻找关键路径