数据结构与算法实验报告（六）

图的基本操作实现 — 邻接矩阵 + 邻接表 + 非递归DFS

苗夕远 · 数据结构与算法 · 第6章实验

一、实验思想

图（Graph）是一种比线性表和树更为复杂的数据结构，其节点之间可以有任意多的连接关系。图在计算机科学中有着广泛的应用，例如社交网络分析、地图导航、网络拓扑等领域。

本实验的核心思想是：通过两种不同的存储结构——邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）——分别实现无向图/网的基本操作，并在此基础上实现图的深度优先遍历（DFS）的非递归版本。通过对比两种存储结构的特点，加深对图的逻辑结构和物理存储的理解。

邻接矩阵

使用一个二维数组（矩阵）存储图中各顶点之间的邻接关系。对于带权无向网，矩阵中元素 $G.arcs[i][j]$ 表示从顶点 $i$ 到 $j$ 的边的权值（当无边时记为无穷大 $\infty$）。邻接矩阵的优点是判断两顶点是否相邻的时间复杂度为 $O(1)$，缺点是空间复杂度为 $O(n^2)$，不适合存储稀疏图。

邻接表

使用一个一维数组存储所有顶点，每个顶点关联一个链表，链表中存储该顶点的所有邻接点。邻接表的空间复杂度为 $O(n + e)$（$e$ 为边数），适合存储稀疏图，但判断两顶点是否相邻需要遍历链表。

选做：非递归DFS

深度优先遍历（DFS）通常使用递归实现，其本质是利用系统栈进行回溯。本实验选做部分要求使用显式栈模拟递归过程，实现非递归的深度优先遍历，从而加深对遍历过程中栈作用的理解。

二、实验结构设计

2.1 全局宏与类型定义

名称值说明
MaxInt32767表示无穷大（无边连接）
MVNum100最大顶点数
OK / ERROR1 / 0函数返回值状态
Statustypedef int Status函数返回类型

2.2 邻接矩阵存储结构

typedef char VerTexType;              // 顶点类型（字符）
typedef int  ArcType;                 // 边的权值类型

typedef struct {
    VerTexType vexs[MVNum];           // 顶点表
    ArcType    arcs[MVNum][MVNum];    // 邻接矩阵
    int vexnum;                       // 当前顶点数
    int arcnum;                       // 当前边数
} AMGraph;

2.3 邻接表存储结构

typedef struct ArcNode {              // 边结点
    int adjvex;                       // 邻接点下标
    struct ArcNode *nextarc;          // 下一指针
} ArcNode;

typedef struct VNode {                // 顶点结点
    int data;
    ArcNode *firstarc;                // 第一条边
} VNode, AdjList[MVNum];

typedef struct {
    AdjList vertices;                 // 邻接表
    int vexnum, arcnum;
} ALGraph;

2.4 栈结构（用于非递归DFS）

typedef struct { int *base; int top; } SqStack;

2.5 函数架构总览

类别函数名功能
邻接矩阵
(AMGraph)		LocateVex查找顶点下标
CreateUDN创建无向网（带权）
InsertVex增加顶点
DeleteVex删除顶点及关联边（交换策略）
InsertArc增加边
DeleteArc删除边
邻接表
(ALGraph)		insertArcNode头插边结点
deleteArcNode删除指定邻接点
freeArcList释放顶点链表内存
CreateALGraph创建无向图
InsertVex / DeleteVex增删顶点
InsertArc / DeleteArc增删边
选做DFS非递归深度优先遍历
栈操作InitStack / DestroyStack
Push / Pop / StackEmpty		栈基本操作
测试TestAMGraph / TestALGraph测试两种存储结构

三、实验过程实现

3.1 邻接矩阵的实现

3.1.1 创建无向网（CreateUDN）

首先输入顶点数与边数；再依次输入各顶点字符；初始化邻接矩阵全为 MaxInt；最后逐条读入边的两个端点和权值，填充对称矩阵。

Status CreateUDN(AMGraph &G) {
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; ++i) cin >> G.vexs[i];
    for (int i = 0; i < G.vexnum; ++i)
        for (int j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;
    for (int k = 0; k < G.arcnum; ++k) {
        VerTexType v1, v2; ArcType w;
        cin >> v1 >> v2 >> w;
        int i = LocateVex(G, v1), j = LocateVex(G, v2);
        G.arcs[i][j] = w; G.arcs[j][i] = G.arcs[i][j];
    }
    return OK;
}

3.1.2 增加顶点（InsertVex）

在顶点表末尾添加新顶点，新顶点的行和列全置 MaxInt，顶点数加 1。

3.1.3 删除顶点（DeleteVex）— 交换策略

找到待删顶点位置后，将其与最后一个顶点交换，再交换对应的行和列，最后顶点数减 1。避免了 $O(n)$ 的数组平移，时间复杂度降至 $O(n)$（仅交换两行两列）。

Status DeleteVex(AMGraph &G, VerTexType v) {
    int n = G.vexnum, m = LocateVex(G, v);
    swap(G.vexs[m], G.vexs[n - 1]);
    for (int i = 0; i < n; i++) swap(G.arcs[m][i], G.arcs[n - 1][i]);
    for (int i = 0; i < n; i++) swap(G.arcs[i][m], G.arcs[i][n - 1]);
    G.vexnum--; return OK;
}

3.1.4 增删边

增加边时对称赋值权值，边数加 1；删除边时对称置 MaxInt，边数减 1。均需检查顶点合法性。

3.2 邻接表的实现

3.2.1 辅助函数

  • insertArcNode：头插法插入边结点，$O(1)$
  • deleteArcNode：遍历链表删除指定邻接点
  • freeArcList：释放顶点所有边结点内存

3.2.2 创建无向图（CreateALGraph）

输入顶点数和边数，按编号 0..n-1 初始化顶点，逐条读入边的两个端点并在两个方向上分别插入边结点。无向图中一条边对应两个方向的有向边，必须对称插入否则图结构不完整。

Status CreateALGraph(ALGraph &G) {
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; i++) {
        G.vertices[i].data = i;
        G.vertices[i].firstarc = NULL;
    }
    for (int k = 0; k < G.arcnum; k++) {
        int v1, v2; cin >> v1 >> v2;
        // 两个方向各插入一次，保持无向图的对称性
        insertArcNode(G.vertices[v1].firstarc, v2);  // v1 → v2
        insertArcNode(G.vertices[v2].firstarc, v1);  // v2 → v1
    }
    return OK;
}
关键模式：双向插入。 无向图中顶点 A 和 B 之间的边，在邻接表中必须同时存在于 A 的链表和 B 的链表中。如果漏掉其中一侧，将导致遍历结果不正确、路径搜素出现单向连通等问题。

3.2.3 增加边（InsertArc）— 自环与重复边检测

在插入边之前需要进行三重检测：（1）顶点下标合法性检查；（2）自环检测（起点等于终点，在一个顶点上连接自己的边）；（3）重复边检测（边已存在）。这三项检查体现了防御性编程思想，防止非法输入破坏图的完整性。

Status InsertArc(ALGraph &G, int v1, int v2) {
    if (v1 < 0 || v2 < 0 || v1 >= G.vexnum || v2 >= G.vexnum)
        return ERROR;
    if (v1 == v2) return ERROR;                    // 自环检测
    // 重复边检测：遍历 v1 的边链表
    ArcNode *p = G.vertices[v1].firstarc;
    while (p) {
        if (p->adjvex == v2) return ERROR;
        p = p->nextarc;
    }
    insertArcNode(G.vertices[v1].firstarc, v2);     // v1 → v2
    insertArcNode(G.vertices[v2].firstarc, v1);     // v2 → v1
    G.arcnum++;
    return OK;
}
注意：自环检测使用 v1 == v2，重复边检测遍历链表。这两项检查在竞赛和工程中都属于必须处理的边界条件，缺少任何一个都可能导致后续 DFS 或路径算法陷入死循环或重复计数。

3.2.4 删除顶点（DeleteVex）— 四步法

邻接表删除顶点分为四步：

  1. 清除入边：遍历其他顶点，删除指向待删顶点的边，统计减少的边数
  2. 释放出边：释放待删顶点自身的边链表
  3. 覆盖顶点：用最后一个顶点覆盖待删顶点
  4. 更新引用：将所有指向最后一个顶点的边更新为指向新位置

3.3 选做：非递归深度优先遍历

算法思想

递归DFS的系统栈行为：访问顶点 → 邻接点压栈 → 弹出栈顶 → 递归处理。非递归版本使用显式栈模拟。

关键技巧：逆序入栈

为保证访问顺序与递归DFS一致，需将邻接点逆序压入栈（临时数组缓存后反向入栈）。

void DFS(ALGraph G, int v) {
    bool visited[MVNum] = {false};
    SqStack S; InitStack(S); Push(S, v);
    while (!StackEmpty(S)) {
        int k; Pop(S, k);
        if (!visited[k]) {
            cout << G.vertices[k].data << " ";
            visited[k] = true;
            ArcNode *p = G.vertices[k].firstarc;
            int buf[MVNum], cnt = 0;
            while (p) {
                if (!visited[p->adjvex]) buf[cnt++] = p->adjvex;
                p = p->nextarc;
            }
            for (int i = cnt - 1; i >= 0; i--) Push(S, buf[i]);
        }
    }
    DestroyStack(S);
}

四、实验结果分析

4.1 编译环境

项目说明
语言标准C++98/03
编译器g++ (MinGW-w64) 15.1.0
编译命令g++ -finput-charset=GBK -o main.exe main.cpp
文件结构单文件，无外部依赖

4.2 测试结果

邻接矩阵 — 创建与增删操作

操作顶点数边数结果说明
创建无向网（A,B,C,D,E）55边：AB/2, AC/3, BD/4, BE/5, CE/6
增加顶点 X5 → 65X的行列全无穷
增加边 X-A（权=5）65 → 6对称赋值
删除边 X-A66 → 5置无穷
删除顶点 X6 → 55X被E覆盖
删除顶点 A（第一个）5 → 45A与E交换后删除，顶点顺序改变
最终矩阵验证：顶点变为 E,B,C,D，边 (E,B)=5, (E,C)=6, (B,D)=4，正确。

邻接表 — 创建与增删操作

操作顶点数边数结果说明
创建无向图（0~5）677条边正确建立
增加顶点 996 → 77空链表
增加边 99-077 → 8双向插入
删除边 99-078 → 7双向删除
添加顶点88,77并连接7 → 97 → 10三角连接 99-88-77-99
删除顶点 999 → 810 → 888与77的边仍保留

选做 — 非递归DFS

创建连通图 0-1-0-2-1-3-1-4-2-5，从不同起点遍历：

非递归DFS（从顶点 0 出发）: 0 2 5 1 4 3
非递归DFS（从顶点 3 出发）: 3 1 4 0 2 5

结果分析与递归DFS一致，验证了逆序入栈策略的正确性。

栈操作实现

非递归 DFS 使用的栈基于动态数组实现，每个操作均为 $O(1)$。关键点在 Push 函数中需要检测栈满（与 MVNum 比较），防止数组越界。

typedef struct { int *base; int top; } SqStack;

Status InitStack(SqStack &S) {
    S.base = new int[MVNum];
    if (!S.base) return OVERFLOW;
    S.top = 0; return OK;
}

Status Push(SqStack &S, int e) {
    if (S.top == MVNum) return ERROR;    // 栈满检测
    S.base[S.top++] = e; return OK;
}

Status Pop(SqStack &S, int &e) {
    if (S.top == 0) return ERROR;        // 栈空检测
    e = S.base[--S.top]; return OK;
}

bool StackEmpty(SqStack S) { return S.top == 0; }

void DestroyStack(SqStack &S) { delete[] S.base; }
设计要点：栈顶指针 top 指向下一空闲位置（而非当前栈顶），因此 Push 时先存值后自增（S.base[S.top++] = e），Pop 时先自减后取值（e = S.base[--S.top]）。这种"空位在顶"的设计与 C++ STL 的 vector::push_back 语义一致。栈满检测 S.top == MVNum 保证了数组不会越界。

4.3 复杂度对比

操作邻接矩阵邻接表
创建$O(n + n^2 + e)$$O(n + e)$
定位顶点$O(n)$$O(n)$
增加顶点$O(n)$$O(1)$
删除顶点$O(n)$（交换策略）$O(n + e)$
增加边$O(1)$$O(1)$（头插法）
删除边$O(1)$$O(d)$（$d$ 为度数）
非递归DFS$O(n^2)$$O(n + e)$
空间$O(n^2)$$O(n + e)$

五、代码分析

5.1 关键代码片段分析

DeleteVex（邻接矩阵）— $O(n)$ 交换策略

传统方法需要将被删顶点之后的所有元素前移，时间复杂度 $O(n^2)$。本实验采用与最后一个顶点交换的策略，仅需 $O(n)$ 时间交换两行两列，常数时间更新顶点数。这种"懒惰删除"手法在算法竞赛和实际系统中被广泛使用。

注意：交换策略改变了顶点的原始顺序。若需要保持顶点顺序不变，则应采用移动而非交换的方式。

DeleteVex（邻接表）— 引用更新

邻接表删除顶点的核心难点：当一个顶点被最后一个顶点覆盖后，所有指向最后一个顶点的边都必须更新为指向新位置。具体做法：遍历每个顶点的边链表，若 $adjvex == G.vexnum - 1$，则将其更新为 $pos$（覆盖位置）。

非递归DFS — 逆序入栈原理

递归DFS中，对于顶点 $v$ 的邻接点 $a_0, a_1, ..., a_{m-1}$，递归调用顺序为先处理 $a_0$，最后处理 $a_{m-1}$。非递归实现中，由于栈的 LIFO 特性，若顺序压入则先弹出 $a_{m-1}$。解决方案：先存储到临时数组，再从后向前入栈（先压 $a_{m-1}$，最后压 $a_0$），弹出时顺序与递归一致。

内存管理

邻接表使用 new 动态分配内存，在 DeleteVex 和 freeArcList 中必须使用 delete 正确释放。覆盖操作 G.vertices[pos] = G.vertices[G.vexnum - 1] 前，被覆盖的最后一个顶点原先的链表指针已被清空，不会造成二次释放或内存泄漏。

六、实验总结

本实验完整实现了图的两种核心存储结构（邻接矩阵和邻接表）的基本操作，并完成了选做的非递归深度优先遍历。通过本实验，加深了对以下知识点的理解：

  1. 图的逻辑结构与存储结构的映射关系：矩阵与链表两种编码方式
  2. 两种存储结构的优劣对比：邻接矩阵以空间换时间，邻接表以时间换空间
  3. 删除操作的边界处理：关联边清理、引用更新、内存释放
  4. 非递归遍历的核心机制：显式栈模拟与逆序入栈技巧
  5. C++ 动态内存管理：new/delete 的正确配对使用
数据结构与算法 · 实验报告（六）· 图的基本操作实现