本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：本文介绍如何利用Qt开发框架对图论中的经典算法进行可视化，涵盖Bellman-Ford算法、Floyd-Warshall算法以及网络单纯形法求解最小费用流问题。通过QGraphicsView、QGraphicsScene和QGraphicsItem等Qt图形组件，构建交互式图形界面，动态展示算法执行过程，如路径松弛、最短路径更新和流量优化。项目“graph_and_network_optimization_qt-master”包含完整的源码与资源文件，适合学习者深入理解图论算法原理及其可视化实现方式。该工具不仅提升算法教学的直观性，也增强了实际编程与问题求解能力。
使用Qt工具将一些图论的算法可视化，目前支持的算法有Bellman，Floyd算法，网络单纯形法求解最小费用流

1. 图论算法可视化概述

图论作为计算机科学与数学交叉领域的重要分支，广泛应用于路径规划、网络流分析、社交网络建模等实际场景。然而，图论算法的抽象性往往使学习者难以理解其内部运行机制。为此，将经典图论算法进行可视化展示成为提升理解效率的关键手段。

本章系统阐述图论算法可视化的意义与价值，重点介绍Bellman-Ford算法、Floyd-Warshall算法以及网络单纯形法在最小费用流问题中的核心地位。传统文本输出方式仅能提供静态结果，缺乏对算法动态演进过程的直观呈现，难以反映松弛操作、矩阵更新或基变换等关键步骤。

通过引入Qt框架构建交互式图形界面，集成动态绘制、实时更新与用户交互功能，可视化系统不仅能清晰呈现算法执行流程，还可辅助教学演示、代码调试与工程验证。例如，节点颜色变化可映射距离估计更新，边的高亮动画可表示增广路径选择，矩阵热力图能直观反映Floyd-Warshall中距离矩阵的演化趋势。

本章为后续理论与实践结合的内容奠定基础，明确整个系统的开发目标：实现一个支持多算法、可扩展、高交互性的图论算法演示平台，具备模块化架构与良好的用户体验设计。

2. Bellman-Ford算法原理与实现

图论中的最短路径问题在现代计算机科学中占据着核心地位，尤其在交通导航、网络路由、资源调度等领域具有广泛的应用背景。其中， Bellman-Ford算法 作为解决 单源最短路径问题 的经典方法之一，因其能够处理带有负权边的图结构而备受关注。相较于Dijkstra算法仅适用于非负权重图，Bellman-Ford具备更强的通用性，尽管其时间复杂度为 $O(V \cdot E)$，略高于Dijkstra，但在特定场景下不可或缺。

本章将深入剖析Bellman-Ford算法的理论基础与执行流程，并结合Qt框架进行工程化实现。通过构建可视化系统，不仅可动态展示每一轮松弛操作对节点距离的影响，还能实时检测负权环的存在，从而提升用户对算法行为的理解深度。整个实现过程涵盖数据结构建模、算法逻辑封装、状态追踪机制以及图形界面映射等多个层面，形成从数学推导到交互呈现的完整闭环。

2.1 Bellman-Ford算法的理论基础

Bellman-Ford算法是基于动态规划思想设计的一种迭代式最短路径求解方法，其核心在于通过多次遍历图中所有边，逐步逼近真实的最短路径值。该算法由Richard Bellman和Lester Ford Jr.分别独立提出，广泛应用于存在负权边但无负权环的图模型中。

2.1.1 单源最短路径问题的形式化定义

单源最短路径（Single-Source Shortest Path, SSSP）问题的目标是从一个指定的源节点 $s$ 出发，计算出它到图中其他所有可达节点 $v \in V$ 的最短路径长度。设图 $G = (V, E)$ 是一个有向或无向带权图，其中 $V$ 表示节点集合，$E$ 表示边集合，每条边 $(u, v) \in E$ 具有权重 $w(u, v)$。目标是找到从 $s$ 到每个 $v$ 的路径 $P$，使得路径上所有边的权重之和最小。

形式化地，令 $d[v]$ 表示当前已知从源点 $s$ 到节点 $v$ 的最短距离估计值。初始时，$d[s] = 0$，其余 $d[v] = \infty$。算法通过不断更新这些估计值，最终收敛至真实最短路径。

值得注意的是，当图中包含负权边时，传统的贪心策略（如Dijkstra）会失效，因为一旦某个节点被标记为“已确定最短距离”，后续无法再修正。而Bellman-Ford允许反复调整距离值，因此能正确处理此类情况。

此外，若图中存在 负权环 （即环路总权重为负），则最短路径可能不存在——绕该环无限循环可使路径长度趋于负无穷。因此，算法必须具备检测此类环的能力，这也是其重要功能之一。

概念 定义
图 $G=(V,E)$ 节点集 $V$ 和边集 $E$ 组成的带权图
权重函数 $w: E \to \mathbb{R}$ 每条边的代价，可正可负
源节点 $s$ 起始查找最短路径的起点
距离数组 $d[\cdot]$ 存储从 $s$ 到各节点的最短距离估计
负权环 总权重小于零的环，导致最短路径无界 
graph TD
    A[Start] --> B[Initialize d[v] = ∞, d[s] = 0]
    B --> C[For i = 1 to |V|-1]
    C --> D[For each edge (u,v) in E]
    D --> E[Relax(u, v, w)]
    E --> F[Check for negative cycle]
    F --> G{Any d[v] updated?}
    G -- Yes --> H[Negative Cycle Detected]
    G -- No --> I[Algorithm Success]

上述流程图清晰展示了Bellman-Ford的整体执行逻辑：初始化后进行 $|V|-1$ 轮松弛操作，最后额外一轮用于检测负权环。

2.1.2 松弛操作的核心机制与数学表达

松弛（Relaxation）是Bellman-Ford算法中最关键的操作，其实质是对当前最短距离估计值的一次优化尝试。对于任意一条边 $(u, v)$，如果通过 $u$ 到达 $v$ 的路径比目前已知的更短，则更新 $d[v]$。

数学表达如下：

\text{if } d[u] + w(u, v) < d[v], \quad \text{then } d[v] \leftarrow d[u] + w(u, v)

这一过程称为“松弛”，意味着我们“放松”了对 $d[v]$ 的限制，使其变得更小。该操作依据三角不等式的思想：两点之间的直接距离不应大于经过第三点的间接路径。

在代码层面，松弛操作通常封装为一个独立函数：

bool relax(int u, int v, double weight, QVector<double>& dist, QVector<int>& prev) {
    if (dist[u] != std::numeric_limits<double>::max() && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        prev[v] = u;
        return true; // 更新发生
    }
    return false;
}

逐行解析：

  1. dist[u] != std::numeric_limits<double>::max() ：判断节点 $u$ 是否已被访问过（即是否可达）。若不可达，则跳过。
  2. dist[u] + weight < dist[v] ：判断是否存在更优路径。
  3. dist[v] = dist[u] + weight ：更新最短距离。
  4. prev[v] = u ：记录前驱节点，用于路径重建。
  5. 返回布尔值表示本次是否发生了更新，便于后续负权环检测使用。

该操作在整个算法中会被重复调用 $|V|-1$ 次，每次遍历所有边。由于每一次迭代都可能传播新的最短路径信息，因此最多需要 $|V|-1$ 次即可确保所有最短路径都被发现（假设无负权环）。

例如，在一个链状图 $s \to a \to b \to c$ 中，若只进行一次边遍历，可能只能更新 $a$；第二次才能更新 $b$；第三次才更新 $c$。因此，$|V|-1$ 次迭代是最坏情况下的必要保障。

2.1.3 负权环检测的必要性与判定条件

虽然Bellman-Ford可以处理负权边，但不能容忍负权环的存在，否则最短路径将失去意义。因此，算法的最后一部分必须进行负权环检测。

判定条件： 在完成 $|V|-1$ 轮正常松弛之后，再次遍历所有边。如果仍存在某条边 $(u, v)$ 满足：
d[u] + w(u, v) < d[v]
则说明图中存在可以从源点到达的负权环。

这是因为，在无负权环的情况下，最短路径最多包含 $|V|-1$ 条边，因此 $|V|-1$ 次迭代足以收敛。若第 $|V|$ 次仍可更新，意味着存在无限缩短路径的可能性。

以下是一个典型的检测代码片段：

bool hasNegativeCycle(const QVector<std::pair<std::pair<int, int>, double>>& edges,
                      const QVector<double>& dist) {
    for (const auto& edge : edges) {
        int u = edge.first.first;
        int v = edge.first.second;
        double w = edge.second;
        if (dist[u] != std::numeric_limits<double>::max() && dist[u] + w < dist[v]) {
            return true; // 存在负权环
        }
    }
    return false;
}

参数说明：

  • edges ：存储所有边的列表，格式为 (u, v), weight
  • dist ：已完成 $|V|-1$ 轮松弛后的距离数组
  • 使用标准库最大值表示无穷大（不可达）

此函数返回布尔值，指示是否存在负权环。若返回 true ，可视化系统应立即停止算法并高亮相关区域，提示用户注意。

负权环的存在不仅影响最短路径结果，也反映了现实系统中的异常，例如金融套利路径、信号反馈回路等。因此，准确检测并定位负权环具有实际工程价值。

2.2 算法流程的逐步解析

理解Bellman-Ford的宏观流程有助于将其转化为可执行的程序逻辑。本节将分步模拟算法运行过程，揭示其内在工作机制。

2.2.1 初始化距离数组与前驱节点记录

算法启动前，需对距离数组 $d[\cdot]$ 和前驱数组 $prev[\cdot]$ 进行初始化。这是所有最短路径算法的共性步骤。

具体做法如下：

  • 设定源节点 $s$ 的距离为 0：$d[s] = 0$
  • 其他所有节点的距离设为无穷大：$d[v] = \infty$
  • 所有节点的前驱设为 -1（表示尚未确定）

在C++中可用Qt容器实现：

QVector<double> dist(numVertices, std::numeric_limits<double>::max());
QVector<int> prev(numVertices, -1);
dist[source] = 0.0;

逻辑分析：

  • numVertices 为图中节点总数
  • 使用 std::numeric_limits<double>::max() 表示无穷大，避免使用特殊魔法数字
  • prev 数组用于最终路径重构，例如从目标节点回溯至源点

初始化完成后，系统进入主循环阶段。

2.2.2 多轮松弛迭代的过程模拟

主循环执行 $|V|-1$ 次，每次遍历所有边并尝试松弛。这一过程体现了算法的“渐进式优化”特性。

for (int i = 0; i < numVertices - 1; ++i) {
    bool updated = false;
    for (const auto& edge : edges) {
        int u = edge.first.first;
        int v = edge.first.second;
        double w = edge.second;
        if (relax(u, v, w, dist, prev)) {
            updated = true;
        }
    }
    if (!updated) break; // 提前终止优化
}

逐行解读：

  1. 外层循环控制迭代次数，最多 $|V|-1$ 次
  2. 内层循环遍历所有边
  3. 调用 relax() 函数尝试更新
  4. 若某轮未发生任何更新，说明已收敛，可提前退出（优化手段）

这种提前终止机制显著提升了稀疏图上的性能表现。例如，在树形结构或链式图中，往往只需几次迭代即可完成。

考虑如下图例：

A --2--> B --(-3)--> C
 ↑               ↖   ↓
 +--------1--------+

若源点为 A，则第一轮松弛后：

  • A→B: d[B]=2
  • B→C: d[C]=-1
  • C→A: d[A] 不变（已有0）

第二轮：

  • A→B: 仍为2
  • B→C: 已最优
  • C→A: d[C]+1 = 0 → 可更新？否（等于原值）

第三轮无变化，算法结束。

2.2.3 终止条件判断与结果有效性验证

完成主循环后，必须执行最后一次全边扫描以检测负权环：

if (hasNegativeCycle(edges, dist)) {
    qDebug() << "Graph contains a negative-weight cycle!";
    return {}; // 返回空结果
}

若未检测到负权环，则 dist 数组即为最终的最短路径结果。此时可通过 prev 数组重构任意节点的最短路径：

QList<int> getPath(int target, const QVector<int>& prev) {
    QList<int> path;
    for (int v = target; v != -1; v = prev[v]) {
        path.prepend(v);
    }
    return path;
}

该函数从目标节点反向追溯至源点，构建完整路径序列。

整个算法的输出包括：

输出项 说明
dist[] 各节点最短距离
prev[] 前驱节点索引
path 特定目标的路径节点列表
异常标志 是否存在负权环

这些信息均可在Qt界面中以颜色编码、文字提示、动画轨迹等形式呈现，极大增强用户的感知能力。

2.3 基于Qt的数据结构建模与代码实现

在Qt环境中实现Bellman-Ford算法，不仅要关注算法逻辑，还需合理组织数据结构以支持可视化交互。

2.3.1 图结构的邻接表表示与内存管理

采用邻接表存储图结构是平衡空间效率与访问速度的最佳选择。在Qt中，可使用 QVector<QMap<int, double>> 实现：

QVector<QMap<int, double>> adjList;
// adjList[u][v] = weight 表示 u→v 的边权

优势：

  • 快速查找邻居节点及其权重
  • 支持稀疏图高效存储
  • QMap 自动排序，便于调试

初始化示例：

adjList.resize(5); // 5个节点
adjList[0][1] = 2.0;
adjList[1][2] = -3.0;
adjList[2][0] = 1.0;

相比二维数组，邻接表节省大量内存，尤其适合大规模图。

2.3.2 使用QVector和QMap组织节点与边权重

除了邻接表，还可维护全局边列表以便于迭代：

struct Edge {
    int from, to;
    double weight;
};
QVector<Edge> edgeList;

该结构便于在Bellman-Ford主循环中统一处理所有边：

for (int i = 0; i < numVertices - 1; ++i) {
    bool changed = false;
    for (const Edge& e : edgeList) {
        if (dist[e.from] + e.weight < dist[e.to]) {
            dist[e.to] = dist[e.from] + e.weight;
            prev[e.to] = e.from;
            changed = true;
        }
    }
    if (!changed) break;
}

使用 QVector<Edge> 提高了缓存局部性，减少指针跳转开销。

2.3.3 算法主循环的封装与状态返回设计

为便于与GUI模块交互，应将算法封装为类：

class BellmanFordSolver {
public:
    struct Result {
        QVector<double> distances;
        QVector<int> predecessors;
        bool hasNegativeCycle = false;
        QString log;
    };

    Result solve(const QVector<Edge>& edges, int numVertices, int source);
};

solve() 方法返回结构化结果，包含距离、前驱、日志等信息，供Qt视图组件消费。

2.4 可视化映射与执行追踪

2.4.1 每一轮迭代中节点颜色变化的语义映射

在Qt界面中，可通过颜色编码反映节点状态：

颜色 含义
绿色 源节点
蓝色 当前正在处理
灰色 已完成更新
红色 处于负权环中

使用 QGraphicsItem::setBrush() 动态修改节点填充色：

nodeItem->setBrush(Qt::blue);

每轮迭代结束后触发场景重绘，体现状态演进。

2.4.2 边的高亮显示与松弛过程动画控制

当某条边被用于松弛时，可在界面上短暂高亮：

edgeItem->setPen(QPen(Qt::red, 3)); // 加粗红色
QTimer::singleShot(500, [edgeItem]() {
    edgeItem->setPen(QPen(Qt::black, 1)); // 恢复
});

配合滑动条调节动画延迟，实现可控节奏演示。

2.4.3 文字提示与日志输出同步机制

通过自定义信号将算法状态推送至日志面板：

signals:
    void logMessage(QString msg);
    void iterationUpdated(int iter);

// 在算法中发射
emit logMessage(QString("Relaxed edge (%1→%2)").arg(u).arg(v));

主窗口连接槽函数，实时更新文本框内容，形成完整的反馈链条。

3. Floyd-Warshall算法原理与实现

在图论中，最短路径问题是最核心的研究方向之一。当需求从单一源点扩展至任意两个节点之间的最短距离时，传统的单源最短路径算法（如Dijkstra或Bellman-Ford）便不再高效。此时，Floyd-Warshall算法以其简洁的结构和强大的功能脱颖而出，成为解决 所有节点对之间最短路径问题 的经典方法。该算法基于动态规划思想，通过三重嵌套循环逐步更新距离矩阵，能够在包含负权边但不含负权环的有向图或无向图中准确计算出每一对顶点间的最短路径长度，并支持路径重建。更重要的是，其天然的矩阵运算形式为可视化提供了良好基础——每一次迭代都对应着全局状态的一次演进，非常适合以热力图、动画高亮等方式呈现。

本章将深入剖析Floyd-Warshall算法的理论框架与关键步骤，结合Qt平台进行工程化实现，重点探讨如何利用二维数据结构高效存储状态信息，优化大规模图的运行性能，并设计直观的用户界面反馈机制，使抽象的数学过程变得可感知、可交互。整个系统不仅服务于教学演示，也可作为复杂网络分析工具的基础组件。

3.1 Floyd-Warshall算法的理论框架

3.1.1 所有节点对之间的最短路径问题建模

在现实世界中，许多应用场景需要快速查询任意两点之间的最优路径，例如城市交通导航系统中的多起点-多终点路线推荐、社交网络中用户间关系链的最短连接、通信网络中数据包转发的延迟最小化等。这类问题统称为“所有节点对之间的最短路径”（All-Pairs Shortest Paths, APSP）。与单源最短路径不同，APSP要求我们一次性求解图 $ G = (V, E) $ 中所有顶点对 $ (i, j) \in V \times V $ 的最短距离 $ d(i, j) $。

设图中有 $ n $ 个节点，用邻接矩阵 $ W $ 表示初始权重：
W[i][j] =
\begin{cases}
0 & i = j \
w(i,j) & (i,j) \in E \
\infty & \text{otherwise}
\end{cases}
其中 $ w(i,j) $ 是边 $ (i,j) $ 的权重。目标是构造一个距离矩阵 $ D $，使得 $ D[i][j] $ 最终等于从节点 $ i $ 到节点 $ j $ 的最短路径长度。

传统做法是对每个节点执行一次Dijkstra算法（适用于非负权图），时间复杂度为 $ O(n^3) $（使用邻接矩阵）或 $ O(nm + n^2 \log n) $（使用优先队列）。但在存在负权边的情况下，Dijkstra失效，而Bellman-Ford虽可处理，但总时间复杂度达到 $ O(n^2 m) $，效率低下。相比之下，Floyd-Warshall算法以统一的方式处理正负权重，只要图中不存在负权环即可正确运行，且代码实现极为简洁，适合集成于图形化系统中。

方法 时间复杂度 能否处理负权 是否适合APSP
Dijkstra（逐点运行） $ O(n^3) $ 或 $ O(n^2 \log n + nm) $ 否 是（仅限非负权）
Bellman-Ford（逐点运行） $ O(n^2 m) $ 是 是
Floyd-Warshall $ O(n^3) $ 是（无负环） 是

可以看出，尽管三者时间复杂度均为立方级，但Floyd-Warshall在负权边场景下具备不可替代的优势，尤其适用于中小型稠密图（即边数接近 $ n^2 $）的应用环境。

此外，Floyd-Warshall还能自然地检测负权环：若最终 $ D[i][i] < 0 $，说明存在从节点 $ i $ 出发并返回自身的负权环。这一特性增强了其在实际工程中的鲁棒性判断能力。

3.1.2 动态规划思想在三重嵌套循环中的体现

Floyd-Warshall算法的核心在于 动态规划 （Dynamic Programming, DP）的思想。它将原问题分解为一系列子问题：考虑只允许经过前 $ k $ 个节点作为中间节点时，任意两节点间的最短路径。随着 $ k $ 从 1 增加到 $ n $，这些中间节点被逐步“激活”，路径选择空间不断扩大，直到覆盖全图。

具体来说，定义状态 $ D_k[i][j] $ 表示从节点 $ i $ 到节点 $ j $，只允许使用节点集合 $ {1, 2, …, k} $ 作为中间节点时的最短路径长度。则状态转移方程如下：

D_k[i][j] = \min(D_{k-1}[i][j],\ D_{k-1}[i][k] + D_{k-1}[k][j])

这表示：要么不经过节点 $ k $，保持原来的最短路径；要么经过 $ k $，将其拆分为 $ i \to k $ 和 $ k \to j $ 两段，取两者之和的最小值。

由于每一层 $ k $ 的更新仅依赖于上一层 $ k-1 $，我们可以直接在原矩阵上就地更新，从而省去额外的空间开销。这就是著名的“滚动数组”技巧在DP中的典型应用。

下面是一个简单的伪代码描述：

for (k = 0; k < n; k++)
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (D[i][k] + D[k][j] < D[i][j])
                D[i][j] = D[i][k] + D[k][j];

这个三层循环正是Floyd-Warshall的灵魂所在。外层控制中间节点 $ k $，内层遍历所有可能的起点 $ i $ 和终点 $ j $。每次更新都是对当前已知最短路径的一次“松弛”操作，本质上与Bellman-Ford中的松弛一致，但这里是以全局矩阵的形式批量完成。

值得注意的是，三个循环的顺序必须是 k 在最外层 。这是因为状态转移依赖于前一轮 $ k-1 $ 的完整结果。如果先固定 $ i $ 或 $ j $，可能会导致错误的覆盖，破坏动态规划的状态不变性。

为了更清晰地理解这一过程，可以借助Mermaid流程图展示算法的整体执行逻辑：

graph TD
    A[开始] --> B[初始化距离矩阵D]
    B --> C{k = 0 to n-1}
    C --> D{i = 0 to n-1}
    D --> E{j = 0 to n-1}
    E --> F[比较 D[i][j] 与 D[i][k] + D[k][j]]
    F --> G{是否更小?}
    G -- 是 --> H[D[i][j] = D[i][k] + D[k][j]]
    G -- 否 --> I[保持原值]
    H --> J[继续下一j]
    I --> J
    J --> K{j < n?}
    K -- 是 --> E
    K -- 否 --> L{i < n?}
    L -- 是 --> D
    L -- 否 --> M{k < n?}
    M -- 是 --> C
    M -- 否 --> N[结束，输出D]

该流程图清晰地展现了算法的递推结构：外层 $ k $ 控制中间节点的引入，内层双重循环扫描所有节点对，依据三角不等式原则尝试优化路径。这种层次分明的控制流非常适合在GUI中按步播放，让用户观察每一个中间节点是如何“桥接”原本不通或非最优的路径的。

3.1.3 距离矩阵与路径重建矩阵的协同更新

仅仅知道最短路径的长度是不够的，在大多数实际应用中，还需要能够还原出具体的路径序列。为此，Floyd-Warshall算法通常维护一个 前驱矩阵 （Predecessor Matrix）$ P $，用于记录路径构造信息。

定义 $ P[i][j] $ 表示从节点 $ i $ 到节点 $ j $ 的最短路径上，$ j $ 的直接前驱节点。初始时，若存在边 $ (i,j) $，则 $ P[i][j] = i $；否则为 nullptr 或 -1。每当发生路径更新（即发现更短路径经过节点 $ k $）时，同步更新前驱信息：

if (D[i][k] + D[k][j] < D[i][j]) {
    D[i][j] = D[i][k] + D[k][j];
    P[i][j] = P[k][j]; // 或 P[i][j] = P[i][k] 取决于实现方式
}

另一种常见策略是在每次更新时令 $ P[i][j] = P[i][k] $，表示新路径的最后一段是从 $ k $ 到 $ j $，而 $ i \to k $ 段由 $ P[i][k] $ 给出。

路径重建可通过递归回溯完成：

void printPath(vector<vector<int>>& P, int i, int j) {
    if (i == j) {
        cout << i;
        return;
    }
    if (P[i][j] == -1) {
        cout << "No path";
        return;
    }
    printPath(P, i, P[i][j]);
    cout << " -> " << j;
}

以下表格展示了某4节点图在不同 $ k $ 阶段的距离矩阵与前驱矩阵变化情况（简化示意）：

k D 矩阵变化 P 矩阵变化 说明
0 初始化邻接矩阵 设置直接前驱 只允许直接边
1 更新经节点0可达的路径 修改相应前驱 如 D[2][3] 通过 0 缩短
2 更多间接路径被发现 前驱链延长 形成跨多个节点的路径
3 全局最短路径收敛 完整路径信息建立 所有可能中间节点已考虑

通过同时维护这两个矩阵，Floyd-Warshall不仅能回答“有多远”，还能回答“怎么走”。这对于可视化系统尤为重要——当用户点击某条最短路径时，程序可以根据前驱矩阵反向追踪并高亮整条路径。

3.2 算法关键步骤深入剖析

3.2.1 初始距离矩阵的构造方法

构建初始距离矩阵是Floyd-Warshall算法的第一步，其质量直接影响后续计算的准确性。假设输入图为带权有向图，节点编号从0到 $ n-1 $，我们使用一个 $ n \times n $ 的二维数组 dist 来表示。

初始化规则如下：

  • 对角线元素 dist[i][i] = 0 （自己到自己的距离为0）
  • 若存在边 $ (i,j) $，则 dist[i][j] = weight(i,j)
  • 其余位置设为无穷大（在代码中常用一个极大值如 INT_MAX / 2 表示）

选择 INT_MAX / 2 而不是 INT_MAX 是为了避免后续加法溢出。例如，若 dist[i][k] == INT_MAX 且 dist[k][j] > 0 ，则相加会溢出为负数，造成误判。

以下是Qt中使用 QVector<QVector<qint64>> 构造距离矩阵的示例代码：

#include <QVector>
#include <climits>

const qint64 INF = INT_MAX / 2;

QVector<QVector<qint64>> initDistanceMatrix(int n) {
    QVector<QVector<qint64>> dist(n, QVector<qint64>(n, INF));
    for (int i = 0; i < n; ++i) {
        dist[i][i] = 0;
    }
    return dist;
}

// 添加边
void addEdge(QVector<QVector<qint64>>& dist, int u, int v, qint64 w) {
    dist[u][v] = w;
    // 若为无向图，则 also: dist[v][u] = w;
}

代码逻辑逐行解读：

  1. const qint64 INF = INT_MAX / 2;
    定义“无穷大”常量，防止后续加法溢出。Qt中推荐使用 qint64 保证跨平台兼容性。

  2. QVector<QVector<qint64>> dist(n, QVector<qint64>(n, INF));
    创建 $ n \times n $ 的二维向量，所有元素初始化为 INF 。外层 QVector 存储行，每行是一个 QVector<qint64> 。

  3. for (int i = 0; i < n; ++i) dist[i][i] = 0;
    设置对角线为0，满足自反性。

  4. addEdge() 函数封装边的添加操作，便于外部调用。

此初始化方式简洁高效，特别适合在Qt的图形界面中由用户交互生成图后自动转换为内部数据结构。

3.2.2 中间节点k的引入与状态转移方程

Floyd-Warshall算法的核心在于中间节点 $ k $ 的逐步引入。每一次外层循环相当于“开放”一个新节点作为潜在的中转站，重新评估所有节点对之间是否存在更优路径。

状态转移的关键在于比较现有路径与经过 $ k $ 的路径：

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

参数说明：
- k : 当前允许使用的最大编号中间节点
- i : 起始节点
- j : 终止节点
- dist[i][k] + dist[k][j] : 表示从 $ i $ 经 $ k $ 到 $ j $ 的路径长度
- dist[i][j] : 当前记录的最短距离

该代码的时间复杂度为 $ O(n^3) $，空间复杂度为 $ O(n^2) $，属于典型的“以空间换时间”策略。

值得注意的是，虽然该算法无法像Dijkstra那样提供中间过程的日志，但可以通过在每轮 $ k $ 结束后触发信号，通知UI模块刷新当前距离矩阵的热力图，从而实现“阶段性可视化”。

3.2.3 路径回溯机制与前驱矩阵的应用

为了实现路径重建，需额外维护前驱矩阵 $ P $。以下为完整实现：

QVector<QVector<int>> initPredecessorMatrix(int n) {
    QVector<QVector<int>> pred(n, QVector<int>(n, -1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j && dist[i][j] != INF) {
                pred[i][j] = i;
            }
        }
    }
    return pred;
}

// 在主循环中同步更新
for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
                pred[i][j] = pred[k][j];
            }
        }
    }
}

扩展说明：
pred[i][j] = pred[k][j] 的含义是：从 $ i $ 到 $ j $ 的最短路径最后一步来自 $ k \to j $ 的路径，因此 $ j $ 的前驱应继承自 $ k \to j $ 的前驱。这种方式确保路径链的完整性。

路径重建函数如下：

QList<int> reconstructPath(const QVector<QVector<int>>& pred, int start, int end) {
    QList<int> path;
    if (pred[start][end] == -1 && start != end) return path; // 无路径

    int current = end;
    while (current != start) {
        path.prepend(current);
        current = pred[start][current];
        if (current == -1) break;
    }
    if (current == start) path.prepend(start);
    return path;
}

该函数返回从 start 到 end 的完整路径节点列表，可用于Qt中高亮显示路径上的节点与边。

flowchart LR
    A[用户选择起点和终点] --> B[调用reconstructPath]
    B --> C{是否有路径?}
    C -- 是 --> D[获取路径节点列表]
    D --> E[高亮对应节点和边]
    C -- 否 --> F[提示“不可达”]

该流程体现了算法输出与可视化模块的联动机制，是构建交互式图论系统的基石。

3.3 Qt环境下的高效实现策略

3.3.1 使用二维QVector存储距离与路径信息

在Qt中， QVector 是首选的动态数组容器，相比标准库 std::vector 更深度集成于元对象系统，支持隐式共享（copy-on-write），适合在多线程或GUI环境中安全传递。

采用 QVector<QVector<qint64>> 存储距离矩阵具有以下优势：

  • 连续内存布局，缓存友好
  • 支持随机访问 O(1) ，便于三重循环高效执行
  • 可直接绑定至模型视图架构（如 QTableView ）

示例代码：

class FloydWarshallSolver : public QObject {
    Q_OBJECT
public:
    explicit FloydWarshallSolver(int n, QObject *parent = nullptr)
        : n(n), dist(n, QVector<qint64>(n, INF)), pred(n, QVector<int>(n, -1)) {}

    void addEdge(int u, int v, qint64 w) {
        dist[u][v] = w;
        pred[u][v] = u;
    }

    void run() {
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        if (dist[i][k] + dist[k][j] < dist[i][j]) {
                            dist[i][j] = dist[i][k] + dist[k][j];
                            pred[i][j] = pred[k][j];
                        }
                    }
                }
            }
            emit iterationCompleted(k, dist); // 发送信号更新UI
        }
    }

signals:
    void iterationCompleted(int k, const QVector<QVector<qint64>>& matrix);

private:
    int n;
    QVector<QVector<qint64>> dist;
    QVector<QVector<int>> pred;
};

该类封装了完整的Floyd-Warshall逻辑，并通过信号 iterationCompleted 实现与UI的松耦合通信。

3.3.2 多线程支持下的长时间运行优化

对于较大规模的图（如 $ n > 500 $），$ O(n^3) $ 的时间开销可能导致界面冻结。为此，应将算法运行置于独立线程中。

Qt提供 QThread 和 QtConcurrent 两种方式。推荐使用 QtConcurrent::run 简化并发编程：

#include <QtConcurrent>

void startComputation() {
    auto future = QtConcurrent::run([=]() {
        solver->run(); // 在后台线程运行
    });
    watcher.setFuture(future);
}

QFutureWatcher<void> watcher;
connect(&watcher, &QFutureWatcher<void>::finished, [](){
    QMessageBox::information(nullptr, "完成", "Floyd-Warshall计算完毕");
});

同时，在 run() 中定期检查中断标志，支持用户主动取消：

volatile bool canceled = false;

void run() {
    for (int k = 0; k < n && !canceled; ++k) {
        // ... 主循环
        emit iterationCompleted(k, dist);
        QThread::usleep(10); // 提供调度机会
    }
}

3.3.3 内存占用分析与大规模图的适应性调整

对于 $ n = 1000 $，距离矩阵需存储 $ 10^6 $ 个 qint64 （约8MB），前驱矩阵 $ 10^6 $ 个 int （约4MB），总体可控。但若 $ n > 5000 $，内存将超过200MB，可能影响性能。

应对策略包括：

  • 使用稀疏矩阵压缩（仅适用于稀疏图）
  • 分块计算（Blocked Floyd-Warshall）
  • GPU加速（OpenCL/CUDA）

目前主流实现仍以完整矩阵为主，适用于教学与中小规模工程场景。

3.4 可视化过程设计与用户感知增强

3.4.1 矩阵热力图随迭代变化的动态渲染

利用 QTableWidget 或自定义 QGraphicsItem 可绘制距离矩阵的热力图。颜色深浅反映数值大小，NaN或INF用灰色表示。

void updateHeatmap(const QVector<QVector<qint64>>& mat) {
    for (int i = 0; i < mat.size(); ++i) {
        for (int j = 0; j < mat[i].size(); ++j) {
            double norm = qBound(0.0, (double)(mat[i][j]) / MAX_VAL, 1.0);
            QColor color = QColor::fromHslF(240 * (1 - norm), 1.0, 0.7);
            QTableWidgetItem *item = table->item(i, j);
            item->setBackgroundColor(color);
            item->setText(QString::number(mat[i][j]));
        }
    }
}

3.4.2 当前处理节点与边的闪烁标识

在每轮 $ k $ 开始时，高亮节点 $ k $，并闪烁与其相连的边，提示用户当前“中介节点”的作用。

scene->highlightNode(k, Qt::yellow);
scene->flashEdgesConnectedTo(k);

3.4.3 实时路径查询与子图聚焦功能集成

提供搜索框，用户输入起终点后，自动调用 reconstructPath 并聚焦视图到该路径区域：

void onQueryPath(int src, int dst) {
    auto path = solver->reconstructPath(src, dst);
    graphicsView->zoomToPath(path);
    scene->highlightPath(path);
}

结合上述机制，Floyd-Warshall算法不再是冰冷的数学公式，而是可看、可探、可交互的认知对象。

4. 网络单纯形法求解最小费用流

在图论与运筹学的交叉领域中， 最小费用流问题（Minimum Cost Flow Problem, MCFP） 是一类核心优化模型，广泛应用于物流调度、交通规划、资源分配和通信网络带宽管理等实际系统中。该问题要求在满足节点流量守恒与边容量约束的前提下，寻找一种可行流方案，使得总运输成本最低。相比最短路径或最大流问题，最小费用流融合了“流”与“费用”的双重维度，其求解复杂度更高，但建模能力更强。

传统的线性规划方法虽可形式化处理此类问题，但在大规模稀疏图上效率低下。为此， 网络单纯形法（Network Simplex Method） 作为一种专为图结构设计的改进版单纯形算法，凭借其利用图拓扑特性的高效基操作机制，在实践中展现出显著优势。本章深入剖析最小费用流问题的数学本质，系统阐述网络单纯形法的核心原理，并结合 Qt 平台实现一个具备可视化追踪能力的交互式求解器，帮助用户理解这一高阶图算法的动态演化过程。

4.1 最小费用流问题的数学建模

最小费用流问题建立在有向图 $ G = (V, E) $ 上，其中每个节点代表一个地点或实体，每条边表示连接两个实体的传输通道。不同于普通流问题仅关注流量大小，最小费用流还引入了单位运输成本的概念，从而将优化目标从“能否流通”提升到“如何低成本流通”。

4.1.1 流量守恒约束与容量边界条件

设图中有 $ n = |V| $ 个节点和 $ m = |E| $ 条边。对于每条边 $ (i,j) \in E $，定义以下参数：

  • $ f_{ij} $：从节点 $ i $ 到节点 $ j $ 的实际流量；
  • $ c_{ij} $：单位流量通过边 $ (i,j) $ 所需的成本；
  • $ l_{ij}, u_{ij} $：该边的流量下限与上限（通常 $ l_{ij}=0 $，$ u_{ij} < \infty $）；

同时，对每个节点 $ i \in V $，定义其供需量 $ b_i $：
- 若 $ b_i > 0 $，则为供应节点（源点），表示向外发送 $ b_i $ 单位货物；
- 若 $ b_i < 0 $，则为需求节点（汇点），需接收 $ -b_i $ 单位货物；
- 若 $ b_i = 0 $，则为转运节点，流入等于流出。

基于上述定义，最小费用流的标准数学模型如下：

\begin{aligned}
\text{minimize} &\quad \sum_{(i,j)\in E} c_{ij} f_{ij} \
\text{subject to} &\quad \sum_{j:(i,j)\in E} f_{ij} - \sum_{j:(j,i)\in E} f_{ji} = b_i, \quad \forall i \in V \quad \text{(流量守恒)}\
&\quad l_{ij} \leq f_{ij} \leq u_{ij}, \quad \forall (i,j) \in E \quad \text{(容量约束)}
\end{aligned}

此模型本质上是一个线性规划问题，但由于变量对应图中的边，且约束矩阵具有特殊的网络结构（全幺模性），因此存在专门针对图结构的高效求解算法——网络单纯形法。

为了确保问题有解，必须满足全局供需平衡条件：

\sum_{i \in V} b_i = 0

否则系统无法达到稳态流动。

此外，在编程实现中，常采用邻接表结构存储图数据，并使用结构体封装边信息：

struct Edge {
    int from, to;
    double cost, flow, capacity;
    bool residual; // 是否是残差边
};

该结构便于后续构建残差图并支持反向边更新。

4.1.2 目标函数构建：总费用最小化

目标函数 $ Z = \sum c_{ij} f_{ij} $ 表示整个网络中所有边上发生的运输总成本。它是一个关于流量变量的线性函数，体现了经济性原则。例如，在电力网络中，$ c_{ij} $ 可能代表单位电量在线路上的能量损耗；在供应链中，则可能是单位商品的运费。

值得注意的是，即使某条边的单位成本较低，也不能无限增加其流量，因为受到容量上限和整体网络平衡的制约。这就形成了一个多因素权衡的过程——既要选择低价路径，又要避免拥堵。

在 Qt 界面中，可以通过滑动条或输入框让用户设置每条边的 cost 和 capacity ，并通过颜色深浅编码成本高低（如蓝色越深表示成本越高），增强直观感知。

参数名 类型 含义说明
from , to int 起始与终止节点编号
cost double 单位流量传输成本
capacity double 最大允许流量
flow double 当前已分配流量
residual bool 标记是否为原边或反向残差边

这种参数组织方式有利于后期集成进 QGraphicsScene 中进行动态渲染与状态同步。

4.1.3 图模型中供需节点的设定规则

在构建实例时，合理设定供需分布至关重要。常见策略包括：

  1. 单源多汇模式 ：设定一个主供应点（如工厂），多个消费点（如零售店），适用于配送系统。
  2. 多源多汇模式 ：多个产地与销地共存，更贴近现实市场结构。
  3. 循环流模式 ：部分节点既产又耗，模拟再制造或回收流程。

在 Qt 实现中，可通过右键菜单为节点添加“设为供应点”或“设为需求点”选项，并弹出对话框输入具体数值。界面应实时校验总供需是否平衡，并提示错误。

例如，若用户设置了总供应量大于总需求量，则系统应阻止算法启动并高亮异常节点。

此外，可以借助 Mermaid 流程图展示一个典型最小费用流问题的构建流程：

graph TD
    A[创建空图] --> B[添加节点]
    B --> C[设置节点类型: 源/汇/转运]
    C --> D[连接边并配置: 成本, 容量]
    D --> E[验证供需平衡 ∑b_i = 0?]
    E -- 是 --> F[初始化可行流]
    E -- 否 --> G[提示错误并返回修改]
    F --> H[进入网络单纯形迭代]

此流程清晰表达了从建模到求解的逻辑链条，有助于开发者与使用者共同理解系统行为。

4.2 网络单纯形法的基本原理

网络单纯形法脱胎于传统线性规划中的单纯形法，但充分利用了图的树结构特性，极大提升了计算效率。其核心思想是： 始终保持一个以生成树为基础的基可行解，并通过不断替换边来降低目标函数值，直到达到最优。

4.2.1 基可行解的树结构表示

在网络流问题中，一个非退化的基对应图的一个 支撑树（Spanning Tree） 加上若干基本非树边。由于流量守恒方程之间线性相关（总和为零），独立方程数为 $ n-1 $，因此基中恰好包含 $ n-1 $ 条边，构成一棵生成树。

这棵生成树上的边称为 基本边（basic arcs） ，其余为 非基本边（non-basic arcs） 。基本边的流量由供需关系唯一确定，而非基本边的流量被固定在其上下界之一（通常是下界 0）。

关键性质： 任何基可行解都对应一个以这些基本边构成的无环连通子图（即生成树） 。

在 Qt 可视化中，可用绿色粗线表示当前基中的边，灰色细线表示非基本边，红色虚线表示负检验数边（潜在入基边）。随着迭代推进，树结构会动态变化，形成明显的“边交换”动画效果。

4.2.2 对偶变量计算与检验数判断

网络单纯形法通过检查非基本边的 检验数（reduced cost） 决定是否需要换入新边。若所有非基本边的检验数均非负，则当前解为最优。

检验数的计算依赖于 节点势（dual variables） $ \pi_i $，它们满足：

c_{ij}^r = c_{ij} - (\pi_i - \pi_j)

其中 $ c_{ij}^r $ 是边 $ (i,j) $ 的约化成本。若 $ c_{ij}^r < 0 $，说明将该边加入基可能降低总成本。

初始势可通过任选一个参考节点（如根节点）设 $ \pi_r = 0 $，然后沿生成树 DFS 遍历计算其余节点：

void computePotentials(int u, double parentPi) {
    pi[u] = parentPi;
    for (auto &edge : treeEdges[u]) {
        int v = (edge.from == u) ? edge.to : edge.from;
        if (abs(pi[v] - INF) < 1e-6) { // 未访问
            double cost = (edge.from == u) ? edge.cost : -edge.cost;
            computePotentials(v, pi[u] + cost);
        }
    }
}

代码逻辑逐行解读 ：

  • 第 2 行：将当前节点 $ u $ 的势设为父节点传递下来的值；
  • 第 3 行：遍历所有属于生成树的邻接边；
  • 第 4 行：确定子节点 $ v $，注意边方向可能反转；
  • 第 5 行：判断 $ v $ 是否已被访问（用 INF 初始化标记）；
  • 第 7 行：根据边的方向调整符号，保证 $ \pi_j = \pi_i + c_{ij} $ 成立。

该递归过程时间复杂度为 $ O(n) $，可在每次基变换后快速更新。

4.2.3 增广路径选择与基变换操作

当发现某非基本边 $ (k,l) $ 的约化成本 $ c_{kl}^r < 0 $，即可将其作为 入基边 。将其加入当前生成树后，必然形成唯一一个环路（fundamental cycle）。沿着该环调整流量，直到某条基本边流量达到边界（饱和或归零），该边即为 出基边 。

随后执行 基变换（pivot operation） ：移除出基边，保留入基边，更新生成树结构与流量分布。

此过程可通过深度优先搜索识别环路：

vector<int> findCycle(int u, int target, int parent, vector<int>& path) {
    path.push_back(u);
    if (u == target && path.size() > 1) return path;

    for (auto &e : adj[u]) {
        int v = (e.to == u) ? e.from : e.to;
        if (v == parent || !inTree(e)) continue;
        auto res = findCycle(v, target, u, path);
        if (!res.empty()) return res;
    }
    path.pop_back();
    return {};
}

参数说明 ：

  • u : 当前搜索节点；
  • target : 入基边另一端点；
  • parent : 防止回溯；
  • path : 记录路径；
  • inTree(e) : 判断边是否在当前生成树中。

找到环后，计算最大可调整流量 $ \Delta $，并对环上边按方向增减流量。最终完成一次迭代。

4.3 算法实现的关键技术难点

尽管网络单纯形法理论成熟，但在工程实现中仍面临诸多挑战，尤其在精度控制、连通性维护和收敛判定方面需格外谨慎。

4.3.1 循环结构检测与负成本圈识别

当图中存在负成本圈（negative cost cycle）且容量无限时，最小费用流无界。此时应提前检测并终止算法。

可采用 Bellman-Ford算法 在残差图中检测负权环：

bool hasNegativeCycle() {
    vector<double> dist(n, 0); // 全0初始化
    for (int i = 0; i < n - 1; ++i)
        for (auto &e : residualEdges)
            if (dist[e.to] > dist[e.from] + e.cost)
                dist[e.to] = dist[e.from] + e.cost;

    for (auto &e : residualEdges)
        if (dist[e.to] > dist[e.from] + e.cost)
            return true;
    return false;
}

逻辑分析 ：

  • 使用松弛操作传播距离；
  • 若第 $ n $ 轮仍能更新，则存在负环；
  • 初始全0可捕获任意起点出发的负环。

该检测应在初始化阶段运行一次，防止无效迭代。

4.3.2 使用深度优先搜索维护生成树连通性

每次基变换后，必须确保新的边集合仍构成一棵生成树。若简单删除一条边导致断开，则需重新连接。

DFS 可用于验证连通性：

void dfs(int u, vector<bool>& visited) {
    visited[u] = true;
    for (auto &e : treeAdj[u]) {
        int v = (e.from == u) ? e.to : e.from;
        if (!visited[v]) dfs(v, visited);
    }
}
// 调用后检查 visited 是否全为 true

此外，还可结合并查集预判是否会形成环，避免非法插入。

4.3.3 浮点精度误差处理与收敛判据设置

由于成本为浮点数，直接比较 cr < 0 易受舍入误差影响。建议引入容差：

const double EPS = 1e-8;
if (reducedCost < -EPS) { /* 入基 */ }

同时，设置最大迭代次数（如 1000）和目标函数变化阈值防止无限循环。

4.4 Qt平台上的数据驱动实现

Qt 提供强大的 GUI 构建能力，非常适合开发交互式算法演示工具。我们将最小费用流求解过程拆分为多个可视阶段，并通过信号槽机制联动界面元素。

4.4.1 流量与费用参数的图形化输入接口

使用 QDialog 设计属性编辑面板，允许用户双击边或节点弹出设置窗口：

class EdgePropertyDialog : public QDialog {
    Q_OBJECT
public:
    QDoubleSpinBox *costInput;
    QDoubleSpinBox *capacityInput;
    QPushButton *okButton;

    EdgePropertyDialog(Edge* e, QWidget* parent = nullptr) {
        costInput = new QDoubleSpinBox(this);
        costInput->setRange(-1000, 1000); 
        costInput->setValue(e->cost);

        capacityInput = new QDoubleSpinBox(this);
        capacityInput->setRange(0, 1e6);
        capacityInput->setValue(e->capacity);

        okButton = new QPushButton("确认", this);
        connect(okNormally, &QPushButton::clicked, this, &QDialog::accept);
    }
};

用户修改后触发 edgeUpdated(Edge*) 信号，通知场景重绘边标签。

4.4.2 解状态的阶段性保存与回放功能

利用 QVector<SolutionSnapshot> 存储每步迭代的状态，支持“前进/后退”操作：

struct SolutionSnapshot {
    QVector<double> flows;
    QVector<Edge> treeEdges;
    double totalCost;
    int iteration;
};

通过 QSlider 控制播放进度，实现算法过程回溯教学功能。

4.4.3 成本变化曲线图的实时绘制与对比分析

集成 QtCharts 模块绘制目标函数随迭代的变化曲线：

QLineSeries *series = new QLineSeries();
for (int i = 0; i < snapshots.size(); ++i)
    series->append(i, snapshots[i].totalCost);

QChart *chart = new QChart();
chart->addSeries(series);
chart->createDefaultAxes();

嵌入 QGraphicsView 下方区域，形成“图+表”联合呈现界面。

graph LR
    A[用户输入图数据] --> B[初始化基可行解]
    B --> C{检验数全≥0?}
    C -- 否 --> D[选负检验数边入基]
    D --> E[找基本环并调整流量]
    E --> F[更新生成树与势]
    F --> C
    C -- 是 --> G[输出最优流方案]

该流程图完整描绘了网络单纯形法的闭环逻辑，适合嵌入帮助文档或教程页面。

综上所述，网络单纯形法不仅理论深刻，而且在 Qt 环境下具备良好的可视化延展性。通过精细化的状态映射与交互设计，原本晦涩的数学过程得以生动展现，极大提升了学习与调试效率。

5. Qt图形视图框架（QGraphicsView/QGraphicsScene）应用

在现代图形化应用程序开发中，尤其是涉及复杂图结构可视化与交互的系统中，Qt 提供的 QGraphicsView 和 QGraphicsScene 框架成为构建高性能、可扩展 GUI 的核心技术。本章深入剖析该图形视图架构的设计哲学与实现机制，结合图论算法演示平台的实际需求，展示如何利用其强大的图元管理、坐标映射和事件处理能力，支撑大规模图结构的动态渲染与用户交互。

5.1 图形视图体系结构解析

Qt 的图形视图框架由三大核心组件构成： QGraphicsScene 、 QGraphicsView 和 QGraphicsItem ，它们共同构成了一个分层清晰、职责明确的图形系统架构。理解这三者之间的协作关系，是构建高效可视化界面的前提。

5.1.1 QGraphicsScene的图元管理机制

QGraphicsScene 是整个图形系统的“数据容器”，负责存储所有可视化的图元对象（如节点、边、文本标签等），并提供对这些图元的增删查改接口。它不直接参与绘制，而是作为逻辑层存在，管理图元的几何信息、状态以及层级关系。

在图论算法可视化场景中，每个节点通常继承自 QGraphicsEllipseItem ，每条边则可能基于 QGraphicsLineItem 或自定义路径类。当使用 scene->addItem(item) 添加图元后， QGraphicsScene 会维护一个内部的空间索引结构（如 B 树或网格索引），以加速碰撞检测和拾取操作。

// 示例：创建并添加一个圆形节点到场景
QGraphicsEllipseItem* node = new QGraphicsEllipseItem(0, 0, 40, 40);
node->setBrush(Qt::blue);
node->setPen(QPen(Qt::black, 2));
node->setFlag(QGraphicsItem::ItemIsMovable); // 支持拖拽
scene->addItem(node);

代码逻辑逐行分析：

  • 第1行：创建一个直径为40像素的椭圆图元，用于表示图节点。
  • 第2行：设置填充颜色为蓝色，增强视觉辨识度。
  • 第3行：设置黑色描边，宽度为2像素，提升轮廓清晰度。
  • 第4行：启用可移动标志，允许用户通过鼠标拖动该节点。
  • 第5行：将图元加入场景，触发内部空间索引更新。

此外， QGraphicsScene 还支持信号机制，例如 changed() 信号会在图元位置、形状变化时发出，便于监听状态变更。对于算法演示系统而言，可通过连接此信号实现实时刷新路径高亮或重新计算布局。

功能特性 描述
图元管理 支持添加/删除/查找 QGraphicsItem 子类实例
空间索引 内建高效查找机制，优化拾取与碰撞检测性能
事件转发 将鼠标、键盘事件转发给当前焦点图元
范围控制 可设定场景矩形范围（ setSceneRect ）限制可视区域 
graph TD
    A[QGraphicsScene] --> B[管理图元集合]
    A --> C[维护空间索引]
    A --> D[处理图元事件分发]
    A --> E[发射变化信号]
    B --> F[节点 NodeItem]
    B --> G[边 EdgeItem]
    B --> H[标签 TextItem]

该结构确保了即使在上千个图元共存的情况下，仍能保持良好的响应速度。特别是在 Bellman-Ford 或 Floyd-Warshall 算法执行过程中，频繁的状态更新（如颜色变化）不会导致整体卡顿。

5.1.2 QGraphicsView的视口映射与缩放控制

QGraphicsView 是用户看到的“窗口”，即视口（viewport），它是 QGraphicsScene 的观察者。多个 QGraphicsView 可共享同一场景，实现多视角同步浏览，适用于调试或多屏展示场景。

默认情况下， QGraphicsView 自动将场景坐标映射到屏幕像素坐标。开发者可通过 setTransform() 方法手动施加仿射变换，实现平移、缩放、旋转等效果。

以下是一个支持鼠标滚轮缩放的功能实现：

void GraphView::wheelEvent(QWheelEvent *event) {
    const double scaleFactor = 1.15;
    if (event->angleDelta().y() > 0) {
        scale(scaleFactor, scaleFactor);
    } else {
        scale(1 / scaleFactor, 1 / scaleFactor);
    }
}

参数说明：

  • event->angleDelta().y() ：获取垂直滚轮偏移量，正值表示向上滚动（放大），负值表示向下（缩小）。
  • scale(x, y) ：调用 QGraphicsView 的内置函数，在当前变换矩阵上乘以缩放因子。

为了防止无限缩放，建议添加边界检查：

double currentScale = transform().m11(); // 获取x方向缩放系数
if ((currentScale < 0.3 && event->angleDelta().y() < 0) ||
    (currentScale > 3.0 && event->angleDelta().y() > 0))
    return; // 限制最小/最大缩放级别

同时，配合 setDragMode(QGraphicsView::ScrollHandDrag) 可启用抓手模式，用户按住鼠标中键即可拖动画布，极大提升大图浏览体验。

缩放级别 视觉用途
0.3x ~ 0.6x 全局拓扑概览，查看整体连通性
1.0x 标准视图，适合算法步进演示
1.5x ~ 3.0x 局部细节聚焦，观察边权重与节点状态

此外， QGraphicsView 支持 OpenGL 后端加速：

QOpenGLWidget *glWidget = new QOpenGLWidget;
setViewport(glWidget);
setViewportUpdateMode(FullViewportUpdate);

此举可显著提升复杂图元的渲染帧率，尤其在启用抗锯齿和透明度混合时更为明显。

5.1.3 坐标系统转换与事件传播路径

Qt 图形视图框架采用三种主要坐标系统：

  1. Item Coordinates ：相对于图元自身的局部坐标（原点在其左上角或中心）。
  2. Scene Coordinates ：相对于整个 QGraphicsScene 的全局坐标。
  3. View Coordinates ：相对于 QGraphicsView 视口的屏幕像素坐标。

三者之间可通过如下方法相互转换：

// 将视口坐标转为场景坐标
QPointF scenePos = view->mapToScene(event->pos());

// 将场景坐标转为某图元的局部坐标
QPointF itemPos = item->mapFromScene(scenePos);

// 判断某点是否落在图元范围内
if (item->contains(itemPos)) {
    qDebug() << "Hit test successful on node";
}

这一机制在实现精确点击识别时至关重要。例如，在用户点击某节点以查询最短路径时，必须准确判断点击落在哪个节点上。

事件传播路径遵循以下顺序：

sequenceDiagram
    participant View
    participant Scene
    participant Item

    View->>Scene: 接收鼠标事件（如 mousePressEvent）
    Scene->>Item: 查询命中测试（hitTest），找到最顶层图元
    Item-->>Scene: 返回是否接受事件
    Scene-->>View: 若无图元处理，则自身处理

若图元希望响应事件，需重写其虚函数，如：

void NodeItem::mousePressEvent(QGraphicsSceneMouseEvent *event) {
    if (event->button() == Qt::LeftButton) {
        setSelected(true);
        emit clicked(this); // 发出自定义信号
    }
    QGraphicsItem::mousePressEvent(event);
}

此处通过 emit clicked(this) 将事件上升至业务逻辑层，实现“点击节点 → 高亮最短路径”的交互链路。

5.2 场景构建与图元布局算法

构建一个直观且美观的图结构不仅依赖于底层框架，还需合理的布局策略。原始图数据往往仅包含连接关系，缺乏空间坐标，因此需要自动布局算法赋予其二维位置。

5.2.1 随机分布与力导向布局的实现

最简单的初始化方式是随机分布节点：

for (auto node : nodeList) {
    int x = qrand() % 800;
    int y = qrand() % 600;
    node->setPos(x, y);
}

但这种布局容易造成重叠与交叉，影响可读性。更优方案是采用 力导向布局 （Force-Directed Layout），模拟物理系统中的引力与斥力平衡。

核心思想：
- 节点间存在库仑式斥力（反比于距离平方）
- 相邻节点间存在胡克式引力（正比于距离）

迭代公式如下：

\vec{F} {total} = \sum {i \neq j} \frac{k^2}{||p_i - p_j||^2} \cdot \hat{r} {ij}
- \sum {(i,j)\in E} ||p_i - p_j|| \cdot \hat{r}_{ij}

其中 $k$ 为常数，$\hat{r}_{ij}$ 为单位方向向量。

Qt 中可通过定时器驱动迭代：

void ForceDirectedLayout::step() {
    for (auto nodeA : nodes) {
        QPointF force(0, 0);
        for (auto nodeB : nodes) {
            if (nodeA == nodeB) continue;
            QPointF diff = nodeA->pos() - nodeB->pos();
            double dist = qMax(1.0, sqrt(diff.x()*diff.x() + diff.y()*diff.y()));
            // 斥力：远离其他节点
            force += diff * (repulsionStrength / (dist * dist));
        }
        // 引力：拉近邻接节点
        for (auto edge : nodeA->edges()) {
            QPointF to = edge->getOtherEnd(nodeA)->pos();
            QPointF diff = to - nodeA->pos();
            force += diff * attractionStrength;
        }
        nodeA->moveBy(force.x() * damping, force.y() * damping);
    }
}

逻辑分析：

  • 外层循环遍历每个节点。
  • 内层双循环计算总合力，包含非邻居间的斥力与邻居间的引力。
  • 使用 qMax(1.0, ...) 防止除零错误。
  • damping 控制步长衰减，避免震荡不收敛。

运行约 100~300 步后，图结构趋于稳定，形成类树状或环状对称布局。

5.2.2 节点位置自动调整避免重叠

即便使用力导向算法，初始阶段仍可能出现严重重叠。为此可引入后处理机制，在每次布局迭代后检测碰撞并分离。

void resolveOverlaps() {
    for (int i = 0; i < nodes.size(); ++i) {
        for (int j = i+1; j < nodes.size(); ++j) {
            QPointF diff = nodes[i]->pos() - nodes[j]->pos();
            double dist = sqrt(diff.x()*diff.x() + diff.y()*diff.y());
            double minDist = 60; // 半径之和 + 安全间距
            if (dist < minDist) {
                double push = (minDist - dist) / 2;
                QPointF offset = diff.normalized() * push;
                nodes[i]->moveBy(offset.x(), offset.y());
                nodes[j]->moveBy(-offset.x(), -offset.y());
            }
        }
    }
}

此函数应在每次 step() 后调用，逐步推开重叠节点。结合阻尼机制，最终形成清晰排布。

布局类型 优点 缺点
随机布局 实现简单，速度快 可读性差，易重叠
力导向 结构自然，体现聚类 计算量大，收敛慢
层次布局 适合 DAG，方向清晰 不适用于任意图

5.2.3 边的贝塞尔曲线绘制与避障优化

直线边在密集图中极易交叉，降低可读性。采用二次贝塞尔曲线可使边绕开障碍物。

QPainterPath EdgeItem::shape() const {
    QPainterPath path;
    QPointF start = source->pos();
    QPointF end = dest->pos();
    QPointF ctrl((start.x() + end.x())/2, start.y() - 100); // 控制点上移
    path.moveTo(start);
    path.quadTo(ctrl, end);
    return path;
}

在 paint() 函数中使用该路径进行绘制：

void EdgeItem::paint(QPainter *painter, const QStyleOptionGraphicsItem*, QWidget*) {
    painter->setPen(QPen(Qt::black, 2));
    painter->drawPath(shape());
}

为进一步优化，可动态调整控制点高度与弧度，依据边密度自动选择曲率强度。甚至可结合 A* 算法进行真正意义上的“路径避障”，但这会显著增加计算负担。

5.3 性能优化与大规模图渲染策略

随着图规模扩大（>1000 节点），传统全量渲染方式会导致帧率骤降。必须采取多种优化手段维持流畅交互。

5.3.1 视图裁剪与不可见图元的绘制跳过

QGraphicsView 默认会对超出视口的图元跳过绘制，前提是正确设置 boundingRect() 并启用 ItemUsesExtendedStyleOption 标志。

class OptimizedNode : public QGraphicsItem {
public:
    QRectF boundingRect() const override {
        return QRectF(-20, -20, 40, 40); // 精确包围盒
    }

    void paint(QPainter* p, const QStyleOptionGraphicsItem* option, QWidget*) override {
        if (!option->exposedRect.intersects(boundingRect()))
            return; // 裁剪优化：仅绘制可见部分
        // 正常绘制逻辑...
    }
};

option->exposedRect 表示当前需要更新的区域，可用于局部重绘判断。

5.3.2 缓存机制启用与OpenGL后端加速

开启图元缓存可大幅提升静态内容的渲染效率：

nodeItem->setCacheMode(QGraphicsItem::DeviceCoordinateCache);

该模式将图元光栅化为纹理，减少重复矢量计算。对于频繁变化的颜色状态，可改用 ItemCoordinateCache 。

结合 OpenGL 后端：

QGraphicsView view;
view.setViewport(new QOpenGLWidget);
view.setViewportUpdateMode(QGraphicsView::FullViewportUpdate);

测试表明，在 2000 节点场景下，OpenGL 模式比默认软件渲染提速 3~5 倍。

5.3.3 异步加载与分块渲染技术探索

对于超大规模图（>10k 节点），应考虑异步分块加载：

void LazyGraphLoader::loadChunk(int chunkId) {
    QtConcurrent::run([=]() {
        auto newNodes = generateNodes(chunkId);
        QMetaObject::invokeMethod(this, [=]() {
            for (auto n : newNodes) scene->addItem(n);
        }, Qt::QueuedConnection);
    });
}

使用 QtConcurrent::run 在后台线程生成图元，再通过 invokeMethod 回主线程添加，避免阻塞 UI。

还可划分场景为若干 Tile 区域，仅当视口进入某区域时才加载对应图元，类似地图瓦片机制。

优化技术 加速效果 适用场景
视口裁剪 2~3x 大图局部浏览
设备缓存 3~5x 静态或低频变化图元
OpenGL 加速 4~6x 高分辨率复杂绘制
分块异步加载 显著改善响应 超大规模图

综上所述，Qt 图形视图框架不仅提供了基础的绘图能力，更通过灵活的架构设计与丰富的优化选项，支撑起复杂图论算法的高质量可视化需求。合理运用这些机制，可打造兼具性能与美感的交互式教学与研究工具。

6. 节点与边的QGraphicsItem自定义绘制

在构建图论算法可视化系统时，图形界面的核心表现力来源于对图结构中基本元素——节点与边——的精准、灵活且可交互的呈现。Qt 提供了强大的 QGraphicsView 框架用于二维图形渲染，其中 QGraphicsItem 是所有可视图元的基础类。通过继承并扩展 QGraphicsItem 或其子类（如 QGraphicsEllipseItem 和 QGraphicsLineItem ），开发者可以实现高度定制化的节点和边的外观与行为。本章深入探讨如何基于 Qt 的图形视图架构，设计支持状态反馈、动态更新与用户交互的自定义节点与边组件，并通过代码级实现、视觉编码策略及事件联动机制，提升整个系统的可读性与可用性。

6.1 自定义节点类的设计与实现

为了满足图论算法可视化过程中对节点状态动态变化的需求，标准的图形项无法直接支持丰富的语义表达（如颜色映射算法阶段、标签显示ID或权重、鼠标悬停提示等）。因此，必须通过继承 QGraphicsEllipseItem 构建具备扩展能力的自定义节点类。

6.1.1 继承QGraphicsEllipseItem实现圆形节点

创建一个名为 NodeItem 的类，继承自 QGraphicsEllipseItem ，使其天然具备椭圆/圆形绘制能力。该类将封装节点的基本属性：唯一标识符（ID）、坐标位置、半径、当前状态（正常、选中、已访问、错误等）以及文本标签内容。

// nodeitem.h
#ifndef NODEITEM_H
#define NODEITEM_H

#include <QGraphicsEllipseItem>
#include <QGraphicsTextItem>

class NodeItem : public QGraphicsEllipseItem {
public:
    enum NodeState {
        Normal,
        Hovered,
        Selected,
        Visited,
        Error
    };

    explicit NodeItem(int id, qreal x, qreal y, QObject *parent = nullptr);

    void setId(int id);
    int getId() const;

    void setState(NodeState state);
    NodeState getState() const;

    QRectF boundingRect() const override;
    void paint(QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *widget) override;

protected:
    void hoverEnterEvent(QGraphicsSceneHoverEvent *event) override;
    void hoverLeaveEvent(QGraphicsSceneHoverEvent *event) override;
    void mousePressEvent(QGraphicsSceneMouseEvent *event) override;

private:
    int m_id;
    NodeState m_state;
    QGraphicsTextItem *m_textItem;
    static const qreal Radius;
};

#endif // NODEITEM_H

逻辑分析与参数说明：

  • enum NodeState ：定义一组枚举值表示节点可能所处的状态，便于后续根据不同算法步骤设置颜色样式。
  • QGraphicsTextItem *m_textItem ：用于在节点中心绘制文本（通常是节点 ID），独立于主图形项管理，支持字体、颜色等样式调整。
  • boundingRect() 重写 ：明确指定该项占据的空间范围，是 Qt 渲染和碰撞检测的基础。
  • paint() 方法重写 ：控制实际绘图过程，依据当前状态选择不同填充色与边框。
  • 事件处理函数 ： hoverEnterEvent 和 mousePressEvent 实现悬停高亮与点击选中功能。

6.1.2 标签文本、ID编号与状态颜色绑定

在构造函数中完成初始图形配置：

// nodeitem.cpp
#include "nodeitem.h"
#include <QPainter>
#include <QFont>

const qreal NodeItem::Radius = 30;

NodeItem::NodeItem(int id, qreal x, qreal y)
    : QGraphicsEllipseItem(-Radius, -Radius, 2 * Radius, 2 * Radius),
      m_id(id), m_state(Normal), m_textItem(new QGraphicsTextItem(QString::number(id), this))
{
    setPos(x, y);
    setFlag(QGraphicsItem::ItemIsMovable);
    setFlag(QGraphicsItem::ItemIsSelectable);
    setAcceptHoverEvents(true);

    // 设置文本居中
    m_textItem->setFont(QFont("Arial", 10));
    m_textItem->setPos(-m_textItem->boundingRect().width() / 2,
                       -m_textItem->boundingRect().height() / 2);
}

执行逻辑逐行解读：

  • setPos(x, y) ：将节点放置到指定场景坐标位置。
  • setFlag(ItemIsMovable) ：允许用户拖动节点，触发自动重绘连接边。
  • setAcceptHoverEvents(true) ：启用悬停事件捕获。
  • 文本偏移计算 ：通过获取 boundingRect() 尺寸进行中心对齐，确保数字始终位于圆心。

接下来，在 paint() 函数中根据状态决定颜色：

void NodeItem::paint(QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *widget)
{
    QColor fillColor;
    switch (m_state) {
    case Normal:     fillColor = Qt::lightGray; break;
    case Hovered:    fillColor = Qt::cyan; break;
    case Selected:   fillColor = Qt::blue; break;
    case Visited:    fillColor = Qt::green; break;
    case Error:      fillColor = Qt::red; break;
    }

    painter->setBrush(fillColor);
    painter->setPen(QPen(Qt::black, 2));
    painter->drawEllipse(boundingRect());

    // 绘制外框高亮（选中状态）
    if (isSelected()) {
        painter->setPen(QPen(Qt::darkBlue, 3, Qt::DashDotLine));
        painter->drawEllipse(boundingRect().adjusted(-5, -5, 5, 5));
    }
}

此段代码实现了 状态驱动的颜色映射机制 ，使 Bellman-Ford 中“被松弛”的节点变为绿色，Floyd-Warshall 当前 k 节点闪烁蓝色，极大增强可观察性。

状态类型 颜色 应用场景示例
Normal 浅灰 初始未处理节点
Hovered 青色 鼠标悬停预览
Selected 蓝色 用户手动选中或作为源点
Visited 绿色 已完成最短路径计算
Error 红色 检测到负权环或输入异常 
stateDiagram-v2
    [*] --> Normal
    Normal --> Hovered : 鼠标进入
    Hovered --> Normal : 鼠标离开
    Normal --> Selected : 点击选中
    Selected --> Normal : 取消选择
    Normal --> Visited : 算法处理完成
    Any --> Error : 出现异常

上述状态图清晰表达了节点在整个生命周期中的状态迁移路径，为后续动画调度提供依据。

6.1.3 鼠标悬停与选中反馈效果增强

通过重写事件处理器增强交互体验：

void NodeItem::hoverEnterEvent(QGraphicsSceneHoverEvent *event)
{
    m_state = Hovered;
    update(); // 触发重绘
    QGraphicsEllipseItem::hoverEnterEvent(event);
}

void NodeItem::hoverLeaveEvent(QGraphicsSceneHoverEvent *event)
{
    m_state = Normal;
    update();
    QGraphicsEllipseItem::hoverLeaveEvent(event);
}

void NodeItem::mousePressEvent(QGraphicsSceneMouseEvent *event)
{
    m_state = Selected;
    update();
    emit selected(this); // 发送信号通知其他模块
    QGraphicsEllipseItem::mousePressEvent(event);
}

这里引入了一个关键设计模式： 信号发射 。当节点被点击时，发出 selected(NodeItem*) 信号，可被主控窗口接收以更新算法起点或打开属性编辑面板。这种松耦合通信方式符合 Qt 推荐的最佳实践。

此外，还可加入动画效果提升感知质量：

#include <QPropertyAnimation>

// 在 hoverEnter 时放大一点
QPropertyAnimation *anim = new QPropertyAnimation(this, "scale");
anim->setEndValue(1.2);
anim->setDuration(150);
anim->start(QAbstractAnimation::DeleteWhenStopped);

此类微交互动画显著提高用户体验，尤其适用于教学演示场景。

6.2 自定义边类的高级绘制技巧

边不仅是连接两个节点的几何线段，更是承载信息的重要载体，例如权重、流量、方向性和当前是否参与增广路径等。为此需构建继承自 QGraphicsLineItem 的 EdgeItem 类。

6.2.1 基于QGraphicsLineItem的箭头标注

// edgeitem.h
#ifndef EDGEITEM_H
#define EDGEITEM_H

#include <QGraphicsLineItem>
#include <QGraphicsPolygonItem>

class NodeItem;

class EdgeItem : public QGraphicsLineItem {
public:
    EdgeItem(NodeItem *source, NodeItem *target, double weight);

    void adjust(); // 更新线段端点随节点移动
    double getWeight() const { return m_weight; }

    NodeItem* getSource() const { return m_source; }
    NodeItem* getTarget() const { return m_target; }

protected:
    void paint(QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *widget) override;

private:
    NodeItem *m_source;
    NodeItem *m_target;
    double m_weight;
    QGraphicsTextItem *m_label;
    QGraphicsPolygonItem *m_arrowHead;
    void drawArrow(const QLineF &line);
};
#endif

参数说明：

  • adjust() ：每次节点移动后调用，重新计算边的起点和终点（需考虑节点边界而非中心）。
  • drawArrow() ：在目标节点附近绘制三角形箭头，指示方向性。
  • m_label ：显示边权重的文本项。
void EdgeItem::adjust()
{
    if (!m_source || !m_target) return;

    QLineF line(m_source->scenePos(), m_target->scenePos());
    double angle = line.angle();

    // 计算从源节点边缘出发的位置（避开圆形区域）
    QPointF sourcePoint = m_source->scenePos();
    QPointF targetPoint = m_target->scenePos();

    sourcePoint += QPointF(NodeItem::Radius * cos(angle * M_PI / 180),
                           -NodeItem::Radius * sin(angle * M_PI / 180));
    targetPoint -= QPointF(NodeItem::Radius * cos(angle * M_PI / 180),
                           -NodeItem::Radius * sin(angle * M_PI / 180));

    setLine(QLineF(sourcePoint, targetPoint));
    m_label->setPos((sourcePoint + targetPoint) / 2);
    drawArrow(line);
}

该方法保证即使节点被拖动，边仍能准确贴合其轮廓。

6.2.2 权重数值标签的位置自适应定位

权重标签默认置于边中点上方，但若多条边密集交叉可能导致重叠。可通过以下策略优化：

void EdgeItem::updateLabelPosition()
{
    QPointF mid = (line().p1() + line().p2()) / 2;
    qreal offset = 15;
    // 根据斜率垂直偏移，避免压在线上
    QLineF perp = line().normalVector().unitVector();
    perp.setLength(offset);
    m_label->setPos(mid + perp.p2());
}

同时支持双击编辑权重，结合弹出对话框实现数据修改回传。

6.2.3 动态宽度表示流量大小的视觉编码

在网络流算法中，边的粗细可用于编码当前流量占比容量的比例：

void EdgeItem::setFlow(double flow, double capacity)
{
    qreal width = 1 + 8 * (flow / capacity); // 最宽9px
    QPen pen = this->pen();
    pen.setWidthF(width);
    setPen(pen);

    // 颜色渐变：浅蓝→深蓝表示接近饱和
    QColor color = QColor::fromHslF(0.6, 1.0, 0.5 * (1 - flow/capacity) + 0.3);
    pen.setColor(color);
    setPen(pen);
}
流量比例 线宽（px） 颜色亮度 含义
0% 1 高 无流量
50% 5 中 正常传输
≥80% 9 低 接近瓶颈，预警 
graph LR
    A[开始] --> B{流量=0?}
    B -- 是 --> C[细线+亮色]
    B -- 否 --> D{流量≥80%?}
    D -- 是 --> E[粗线+暗色]
    D -- 否 --> F[适中线宽+过渡色]

这一编码方式使得复杂网络中的拥塞状况一目了然。

6.3 交互行为与图形状态联动

可视化系统的价值不仅在于静态展示，更体现在动态交互过程中各组件的状态同步。

6.3.1 拖拽移动节点时边的自动重绘

利用 Qt 的信号机制，在节点移动时通知所有关联边更新：

// nodeitem.cpp
void NodeItem::mouseMoveEvent(QGraphicsSceneMouseEvent *event)
{
    QGraphicsItem::mouseMoveEvent(event);
    emit positionChanged(); // 自定义信号
}

在边类中连接该信号：

connect(m_source, &NodeItem::positionChanged, this, &EdgeItem::adjust);
connect(m_target, &NodeItem::positionChanged, this, &EdgeItem::adjust);

从而实现 实时拓扑维护 ，用户可自由重组图结构用于测试不同布局下的算法性能。

6.3.2 右键菜单弹出与属性编辑响应

重写 contextMenuEvent 实现快捷操作：

void NodeItem::contextMenuEvent(QGraphicsSceneContextMenuEvent *event)
{
    QMenu menu;
    QAction *editAction = menu.addAction("Edit Weight");
    QAction *removeAction = menu.addAction("Remove Node");

    QAction *selectedAction = menu.exec(event->screenPos());
    if (selectedAction == editAction) {
        bool ok;
        double w = QInputDialog::getDouble(nullptr, "Input", "Weight:", 1.0, -100, 100, 2, &ok);
        if (ok) emit weightChanged(this, w);
    } else if (selectedAction == removeAction) {
        emit nodeRemoved(this);
    }
}

此类上下文菜单极大简化了图结构调整流程。

6.3.3 多选操作与批量样式修改支持

启用 ItemIsSelectable 标志后，结合 Shift/Ctrl 键实现多选。可在主窗口监听选择变化：

connect(scene, &QGraphicsScene::selectionChanged, [&]() {
    auto items = scene->selectedItems();
    statusBar()->showMessage(QString("Selected %1 nodes").arg(items.size()));
});

进一步支持批量设置颜色、重置状态或统一调整参数，提升操作效率。

综上所述，通过对 QGraphicsItem 的深度定制，结合状态管理、事件响应与视觉编码技术，成功构建了一套兼具表现力与交互性的图元系统，为后续算法可视化奠定了坚实基础。

7. 信号与槽机制在算法交互中的应用

7.1 Qt信号与槽的基础架构

Qt的信号与槽（Signal and Slot）机制是其元对象系统（Meta-Object System）的核心特性，为GUI组件与后台算法模块之间的松耦合通信提供了强大支持。该机制允许对象在状态变化时发射信号（Signal），而其他对象可通过预定义的槽函数（Slot）响应这些信号，实现事件驱动的程序设计。

在图论算法可视化系统中，信号与槽不仅用于按钮点击、滑动条拖动等基本UI交互，更承担着控制流传递、状态同步和错误反馈等关键职责。其基本语法如下：

// 连接语法示例：C++11风格
connect(sender, &SenderClass::signalName,
        receiver, &ReceiverClass::slotFunction);

// 使用Lambda表达式作为槽函数
connect(ui->startButton, &QPushButton::clicked, this, [this]() {
    startBellmanFord();
});

其中， sender 是发出信号的对象，如 QPushButton ； receiver 是接收并处理信号的对象，如主窗口类实例。Qt 支持多种连接类型，默认为自动连接（ Qt::AutoConnection ），在跨线程场景下可显式指定 Qt::QueuedConnection 以确保线程安全。

信号类型 发送对象 触发条件 典型接收者
clicked() QPushButton 用户点击按钮 主控逻辑类
valueChanged(int) QSlider 滑动条数值改变 动画控制器
customContextMenuRequested(const QPoint&) QGraphicsView 右键菜单请求 节点属性编辑器
algorithmProgress(int) AlgorithmWorker 算法迭代进度更新 状态栏/进度条
pathFound(const QVector &) BellmanFordSolver 找到最短路径 高亮渲染模块
errorOccurred(const QString&) NetworkSimplexSolver 计算异常 日志面板

7.2 用户操作触发算法执行流程

用户通过界面控件发起的操作需转化为对底层算法模块的调用指令，这一过程依赖于精确的信号绑定。

7.2.1 “开始运行”按钮启动Bellman-Ford算法

当用户点击“开始运行”按钮时，系统应验证输入合法性，并启动算法执行线程：

void MainWindow::on_startButton_clicked() {
    if (!graph.isValid()) {
        QMessageBox::warning(this, "输入错误", "图结构不完整或权重非法");
        return;
    }

    // 禁用控件防止重复启动
    ui->startButton->setEnabled(false);
    ui->pauseButton->setEnabled(true);

    // 创建算法工作对象并建立连接
    bellmanFordWorker = new BellmanFordSolver(graph, sourceNode);
    connect(bellmanFordWorker, &BellmanFordSolver::iterationUpdated,
            this, &MainWindow::updateVisualization);
    connect(bellmanFordWorker, &BellmanFordSolver::resultReady,
            this, &MainWindow::displayShortestPath);
    connect(bellmanFordWorker, &BellmanFordSolver::errorOccurred,
            this, &MainWindow::showErrorMessage);

    // 移交至工作线程
    QThread *thread = new QThread;
    bellmanFordWorker->moveToThread(thread);

    connect(thread, &QThread::started, bellmanFordWorker, &BellmanFordSolver::run);
    connect(bellmanFordWorker, &BellmanFordSolver::finished, thread, &QThread::quit);
    connect(thread, &QThread::finished, thread, &QThread::deleteLater);

    thread->start();
}

上述代码展示了如何通过信号将算法进度逐步反馈至UI层，同时保证主线程不被阻塞。

7.2.2 滑动条控制动画速度与步进模式切换

动画播放速度由 QSlider 控制，其值映射为延时毫秒数：

connect(ui->speedSlider, &QSlider::valueChanged, this, [this](int value) {
    int delay = 1000 - value * 10; // 映射为0~1000ms
    emit animationSpeedChanged(delay);
});

此外，系统支持“自动运行”与“单步执行”两种模式，通过 QRadioButton 切换：

connect(ui->stepModeRadio, &QRadioButton::toggled, this, [this](bool checked) {
    if (checked) {
        emit executionModeChanged(ExecutionMode::StepByStep);
    }
});

7.2.3 中断信号发送与算法暂停/恢复机制

为了支持运行中断，算法类需定期检查外部信号：

class BellmanFordSolver : public QObject {
    Q_OBJECT
public slots:
    void pauseRequested() { paused = true; }
    void resumeRequested() { paused = false; notifyCondition.wakeAll(); }

private:
    bool paused = false;
    QWaitCondition notifyCondition;
    QMutex mutex;

    void relaxEdge(...) {
        // ...
        QMutexLocker locker(&mutex);
        while (paused) {
            notifyCondition.wait(&mutex);
        }
    }
};

主界面通过按钮发送暂停/继续信号：

connect(ui->pauseButton, &QPushButton::clicked, worker, &BellmanFordSolver::pauseRequested);
connect(ui->resumeButton, &QPushButton::clicked, worker, &BellmanFordSolver::resumeRequested);

7.3 算法状态反馈至界面的双向同步

算法执行过程中产生的中间状态必须实时反映在图形界面上，形成闭环反馈。

7.3.1 迭代次数更新触发场景重绘

每次完成一轮松弛后，算法发射 iterationUpdated(int iter) 信号：

emit iterationUpdated(currentIteration);

主窗口捕获该信号并通知视图刷新：

void MainWindow::updateVisualization(int iter) {
    scene->updateAllNodeColors();   // 根据最新距离值着色
    scene->updateAllEdgeStyles();   // 高亮被松弛的边
    ui->iterLabel->setText(QString("迭代: %1").arg(iter));
}

7.3.2 最短路径结果通过信号传递给高亮模块

路径计算完成后，返回最优路径边集：

struct PathResult {
    QVector<Edge*> edges;
    double totalCost;
};
emit resultReady(pathResult);

接收端解析路径并启用动画高亮：

void MainWindow::displayShortestPath(const PathResult& result) {
    for (auto edge : result.edges) {
        edge->setHighlighted(true);
    }
    scene->animatePathHighlight(result.edges); // 流光效果
}

7.3.3 错误信息弹窗与日志面板内容推送

异常情况通过统一错误信号传播：

if (hasNegativeCycle) {
    emit errorOccurred("检测到负权环，最短路径无解");
}

日志系统接收并记录：

connect(this, &BellmanFordSolver::errorOccurred, logger, &LogPanel::addError);
connect(this, &BellmanFordSolver::logMessage, logger, &LogPanel::appendInfo);

7.4 完整交互链条的设计与稳定性保障

7.4.1 信号队列管理防止事件堆积

长时间运行算法可能频繁发射信号，导致UI事件队列溢出。解决方案包括节流（throttling）与合并更新：

QTimer throttleTimer;
connect(&throttleTimer, &QTimer::timeout, this, [this]{
    scene->batchUpdate(pendingUpdates);
    pendingUpdates.clear();
});
throttleTimer.start(100); // 每100ms批量刷新一次

7.4.2 多线程环境下信号跨线程安全传递

Qt 的信号槽在跨线程连接时自动使用排队机制。但需注意：
- 槽函数参数必须注册到元系统（ qRegisterMetaType<T>() ）
- 避免传递原始指针，推荐使用智能指针或值类型

qRegisterMetaType<PathResult>("PathResult");

7.4.3 用户误操作防护与状态一致性校验

引入状态机管理界面可用性：

enum AppState {
    Idle,
    Running,
    Paused,
    Finished
};

void setState(AppState newState) {
    currentAppState = newState;
    ui->startButton->setEnabled(newState == Idle);
    ui->pauseButton->setEnabled(newState == Running);
    ui->resetButton->setEnabled(newState != Running);
}

所有信号发射前进行状态检查，避免无效操作引发崩溃。

stateDiagram-v2
    [*] --> Idle
    Idle --> Running : start clicked
    Running --> Paused : pause requested
    Paused --> Running : resume requested
    Running --> Finished : algorithm finished
    Paused --> Finished : cancel clicked
    Finished --> Idle : reset
    Idle --> Idle : invalid input

本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：本文介绍如何利用Qt开发框架对图论中的经典算法进行可视化，涵盖Bellman-Ford算法、Floyd-Warshall算法以及网络单纯形法求解最小费用流问题。通过QGraphicsView、QGraphicsScene和QGraphicsItem等Qt图形组件，构建交互式图形界面，动态展示算法执行过程，如路径松弛、最短路径更新和流量优化。项目“graph_and_network_optimization_qt-master”包含完整的源码与资源文件，适合学习者深入理解图论算法原理及其可视化实现方式。该工具不仅提升算法教学的直观性，也增强了实际编程与问题求解能力。


本文还有配套的精品资源，点击获取
menu-r.4af5f7ec.gif

Logo
开源鸿蒙跨平台开发者社区

开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。

更多推荐

OpenHarmony HDF 传感器驱动：设备休眠唤醒后 Sensor 失效问题修复

在 OpenHarmony 设备上，当系统进入休眠（Suspend）后再次唤醒（Resume）时，加速度传感器（Accelerometer）会出现数据异常或完全失效的问题。具体表现为：这个问题在依赖 Sensor 数据的应用场景中（如屏幕旋转、计步、重力感应等）影响尤为严重，直接导致用户体验中断。加速度传感器芯片（如常见的 LSM6DS3、BMA 系列、ADXL 系列等）通过 I2C/SPI 总线

avatar 开源鸿蒙跨平台开发者社区
cover

GitHub每日热评｜Valhalla静态工程审阅｜零风险！top-welcome-screens 移动端顶级动效启动页源码全量评测【架构拆解+接入方案+避坑指南】

avatar 开源鸿蒙跨平台开发者社区
cover

蓝速科技丨OpenHarmony 信创落地：嵌入式终端国产化突围实战

avatar 开源鸿蒙跨平台开发者社区