基于 C++/Qt6 的图论可视化桌面工具。支持有向图和无向图的文本输入、力导向自动布局、鼠标拖拽交互、自适应顶点圆圈大小，以及 11 种经典图论算法的高亮展示。无第三方依赖（除 Qt 和 C++ 标准库）。
GraphViz/
├── CMakeLists.txt # 根 CMake（C++17，Qt6 Widgets，AUTOMOC）
├── CMakePresets.json # CMake 构建预设（gui）
├── README.md
├── docs/
│ ├── MANUAL.html # 用户使用说明书（随包分发）
│ └── screenshots/ # 界面截图
├── include/ # 公共头文件
│ ├── GraphTypes.h # Vertex / Edge 数据结构
│ ├── Graph.h # 图存储层（邻接表，支持平行边和自环）
│ ├── GraphParser.h # 边格式文本解析器
│ └── GraphAlgorithm.h # 11 种算法声明 + 结果结构体
├── src/ # 实现文件
│ ├── main.cpp # 应用入口
│ ├── Graph.cpp # 图存储实现
│ ├── GraphParser.cpp # 文本解析器实现（手动解析 + 引号名 + 灵活操作符 + 孤立点）
│ ├── GraphAlgorithm.cpp # 所有图论算法实现
│ └── gui/
│ ├── MainWindow.h/cpp # 主窗口（输入面板 + 控制栏 + 菜单）
│ ├── GraphWidget.h/cpp # 图渲染组件（QPainter 自绘）
│ ├── GraphTextEdit.h/cpp # 编辑组件（Shift+Tab 支持）
│ ├── ForceLayout.h/cpp # Fruchterman-Reingold 力导向布局
│ └── UpdateChecker.h/cpp # GitHub API 异步更新检查
├── samples/ # 展示用图数据（入包）
│ └── ...
└── test_data/ # 示例与测试图数据
├── sample.graph # 默认示例图（启动自动加载）
├── euler.graph # 欧拉回路测试图
├── components.graph # 多连通分量测试图
├── parallel.graph # 平行边测试图
├── selfloop.graph # 自环测试图
└── shortestpath.graph # 最短路径测试图
| 组件 | 职责 |
|---|---|
GraphTypes.h |
Vertex（name + 自增 id）、Edge（from/to/weight/directed/id/explicit_weight） |
Graph |
邻接表存储，支持有向/无向混合、平行边、自环。Edge 按唯一 id 去重，hasExplicitWeight() 控制全局权重显示 |
GraphParser |
灵活文本解析：手动字符扫描 + 引号名 + 转义 + 操作符结构校验 + 负权引号格式 + 孤立点 |
GraphAlgorithm |
全部算法静态方法：Dijkstra（多解）、Kruskal、Tarjan、Hierholzer（多解+指定起点）、回溯哈密顿（多解+指定起点）、BFS/Kosaraju 分量、平面性检测、顶点着色（Welsh-Powell + 回溯） |
MainWindow |
菜单栏（文件/编辑/视图/帮助）、左侧编辑面板、控制栏（算法选择/参数/按钮）、状态栏 |
UpdateChecker |
QObject 子类，异步调用 GitHub Releases API 获取最新版本号，语义化版本比较 |
GraphWidget |
QWidget 子类，paintEvent 手绘：节点圆+标签（半径自适应文本 20–80px）、有向箭头、自环弧线、平行边偏移、权重标签分散、高亮着色 |
GraphTextEdit |
QPlainTextEdit 子类，增加 Shift+Tab 前向缩进（Key_Backtab 处理） |
ForceLayout |
Fruchterman-Reingold 算法：环形初始分布（+小幅抖动）、乘法降温 150 次迭代、软边界、平行边端点对去重 |
环境要求：CMake ≥ 3.19，C++17 编译器，Qt 6（Widgets + Network 模块）。
CMakePresets.json 不硬编码编译器或 Qt 路径，机器特定的配置通过 CMakeUserPresets.json 覆盖（模板见 CMakeUserPresets.json.example）。
通过系统包管理器安装 Qt6（如 apt install qt6-base-dev），CMake 自动查找。无需 CMakeUserPresets.json。
git clone https://github.com/SiriLee/GraphViz.git
cd GraphViz
cmake --preset gui -DCMAKE_BUILD_TYPE=Release
cmake --build build-gui --config Release
./build-gui/GraphViz # ELF 二进制，通过 WSLg 或原生 X11/Wayland 显示将 CMakeUserPresets.json.example 复制为 CMakeUserPresets.json，修改其中的 MinGW 编译器路径和 Qt 路径指向本机 Windows 侧安装。WSL 可直接调用 /mnt/d/... 下的 Windows .exe 工具链。
cmake --preset gui-mingw -DCMAKE_BUILD_TYPE=Release
cmake --build build-gui --config Release
./build-gui/GraphViz.exe # Windows PE 可执行文件CMakeLists.txt 中的 if(WIN32) 块在交叉编译成功后会自动执行 windeployqt，将所需 Qt DLL 复制到构建目录。
从 Releases 下载 GraphViz-v*-portable.zip，解压双击 GraphViz.exe，无需安装任何依赖。
每行一条边或一个孤立点，支持 # 行注释和空行。顶点名由字母、数字、中文、下划线组成；含空格、-、<、>、"、# 时必须用 "..." 包裹（内部 \" \\ 转义）。仅含顶点名（无操作符）的行创建孤立点。
| 格式 | 含义 |
|---|---|
A---B |
无向边，权 1.0 |
A-3--B |
无向边，权 3 |
A-->B |
有向边 A→B，权 1.0 |
A->B |
有向边 A→B（最简），权 1.0 |
A<-B |
有向边 B→A（最简），权 1.0 |
A-2.5->B |
有向边 A→B，权 2.5 |
| 格式 | 含义 |
|---|---|
A --- B |
空格分隔 |
A-----B |
多余 - |
A-2-B |
单 - 包裹权重，无向 |
A<-->B |
双向箭头，无向 |
A<---B |
左向箭头，有向 B→A |
A<-3--B |
左向带权，有向 B→A |
"A B"---"C D" |
含空格顶点名 |
"\"X\""---"\"Y\"" |
顶点名 "X" 和 "Y" |
A-"-2"->B |
负权重 -2 |
A---A |
无向自环 |
A-->A |
有向自环 |
| 格式 | 含义 |
|---|---|
2(1)---5 |
顶点 "2"，内部标识 2#1，画布显示 2 |
2(2)---3 |
另一个顶点 "2"，内部标识 2#2，画布显示 2 |
name(N)— N 为非负整数，括号紧贴顶点名末尾- 不含后缀时行为不变（向后兼容）
- 引号名不触发后缀解析
| 格式 | 原因 |
|---|---|
A>-<B |
> 不在末尾 |
A-<-B |
< 不在开头 |
A>--B |
以 > 开头 |
A-3>B |
y 无 -（权重后缺少分隔符） |
A<<--B |
< 出现超过一次 |
A-->>B |
> 出现超过一次 |
A-"abc"->B |
权重不是有效浮点数 |
my-node---B |
顶点名含 - 须加引号 |
| 格式 | 含义 |
|---|---|
A |
无引号孤立点（无空格、无 -） |
"孤立节点" |
引号包裹孤立点（支持任意内容） |
"A-B" |
含 - 的顶点名，引号避免歧义 |
- 一行仅含顶点名无操作符时，创建无边孤立点
- 序列化 (
保存) 同步输出孤立点，加载不丢失 - 力导向布局自动渲染，孤立点受排斥力推向外围
| 区域 | 内容 |
|---|---|
| 左侧面板 | 多行文本编辑器，输入/编辑图数据 |
| 右侧画布 | QPainter 渲染图结构，鼠标可拖拽顶点 |
| 底部控制栏 | 文件操作按钮 + 算法选择 + 参数输入 |
| 菜单栏 | 文件（打开/保存）、编辑（撤销/重做）、视图（重置布局）、帮助（检查更新/打开下载页/使用说明/关于） |
| 快捷键 | 功能 |
|---|---|
Ctrl+Z |
撤销编辑 |
Ctrl+Y |
重做编辑 |
Shift+Tab |
减少缩进 |
Ctrl+O |
打开文件 |
Ctrl+S |
保存文件 |
- 箭头：有向边终点绘制三角形箭头
- 自环：弧线形式渲染在顶点上方
- 平行边：自动垂直偏移 ±7px 分开，权重标签沿边均匀分散
- 权重显示：图中任一边显式提供权重时，全部边显示权值；否则全部隐藏
- 自适应圆圈：顶点圆半径根据标签文本宽度动态计算（QFontMetrics 测量，20–80px 区间），长标签自动放大
- 高亮：每种算法有专属颜色（绿/橙/红紫/蓝/青/多色）
- 检查更新：启动后异步查询 GitHub Releases API，发现有新版本时状态栏持续提示，已是最新或网络异常时自动消失。每日自动检查一次，内置 API 限流守卫。菜单项支持手动触发。
- 打开下载页：调用系统默认浏览器打开 GitHub Releases 页面。
- 使用说明：浏览器打开内置 MANUAL.html（自包含 CSS），提供完整的输入格式参考、快捷键、11 种算法说明和示例图列表。
- 问题反馈：打开浏览器跳转到 GitHub Issues 页面，方便用户提交 bug 或功能建议。
- 关于：显示版本号、项目简介、Qt 运行时版本、GitHub 链接和 MIT 许可证。
| # | 算法 | 方法 | 参数 | 高亮色 |
|---|---|---|---|---|
| 1 | 最短路径 | Dijkstra | 起点 + 终点 | 绿 |
| 2 | 最小生成树 | Kruskal | — | 橙 |
| 3 | 关节点 & 桥 | Tarjan DFS | — | 红节点 / 紫边 |
| 4 | 欧拉回路 | Hierholzer + 回溯 | 起点（可选） | 蓝 |
| 5 | 欧拉通路 | Hierholzer + 回溯 | 起点（可选） | 蓝 |
| 6 | 哈密顿回路 | 回溯 + 剪枝 (≤20) | 起点（可选） | 青 |
| 7 | 哈密顿通路 | 回溯 + 剪枝 (≤20) | 起点（可选） | 青 |
| 8 | 连通分量 | BFS | — | 多色 |
| 9 | 强连通分量 | Kosaraju | — | 多色 |
| 10 | 平面性检测 | Euler公式 + K5/K3,3 | — | 状态栏 |
| 11 | 顶点着色 | Welsh-Powell + 回溯 (≤30) | — | 多色类 |
最短路径 (Dijkstra)
- 支持有向/无向混合图，权重为 double
- 使用
std::priority_queue+std::greater，确定性出队 - 多解支持：前驱 DAG + DFS 回溯枚举所有等权最短路径（上限 50 条），UI 提供「上一解 / 下一解」切换
最小生成树 (Kruskal)
- 仅作用于无向边；DSU 判环
- 不连通图返回
DISCONNECTED
关节点 & 桥 (Tarjan)
- 单次 DFS，预建无向化邻接表确保有向边双向可见
- 桥判定
low[v] > disc[u]，平行边自动去重（须全部断开才判定为桥） - 根节点
children > 1为割点
欧拉回路 / 通路 (Hierholzer + 回溯多解)
- 回路：所有非零度顶点度数为偶 + 连通
- 通路：恰有 0 或 2 个奇度顶点 + 连通
- 自环正确计度数为 2
- 小图 (n≤15, m≤30) 回溯收集多条解，大图贪心单解
- 支持指定起点（from 输入框），回路任意顶点、通路须奇度顶点
哈密顿回路 / 通路 (回溯)
- 顶点数 ≤ 20，超过自动跳过并提示
- 回路从指定起点（或默认首顶点）出发；通路可指定或遍历所有起点
- 收集所有解（上限 100），UI 提供「上一解 / 下一解」切换
平面性检测
- Euler 公式快速否定 (m_unique > 3n-6)
- n≤10 暴力搜索 K5/K3,3 子图
- n≤4 自动判定平面
顶点着色 (Welsh-Powell + 回溯)
- 仅支持无向图，含向边时提示
- Welsh-Powell 贪心：按度降序依次分配最小可用颜色
- 回溯精确求解：≤30 顶点时在贪心上界内搜索真色数，>30 顶点返回贪心近似（
exact=false） - 结果按色类分区高亮
连通分量 (BFS) / 强连通分量 (Kosaraju)
- 分量大小降序排列，各分量独立着色
- 平行边：
addEdge不拒绝同端点同方向边，每条分配唯一id。getAllEdges()按 id 去重（无向边反向拷贝共享 id），保留平行边 - 自环：
from == to时无向边不创建反向拷贝。渲染以弧线形式在顶点上方绘制 - 重叠偏移：同端点组内多条边自动沿垂直方向均匀偏移（步长 7px），权重标签沿边方向分散（组内等分 25%~75%）
采用 Fruchterman-Reingold 算法：
- 分量独立布局：多连通分量图先拆分为独立分量，每个分量在自己的网格单元内运行 FR，互不干扰，彻底解决多分量散落边缘问题
- 初始分布：环形均匀放置（半径 = 35% 短边），每顶点加 ±10px 随机抖动
- 排斥力：所有顶点对之间，
1.0 × k² / dist（标准 FR 公式） - 吸引力：每对邻接顶点仅一次（平行边去重），
dist² / k - 理想边长：
k = 0.8 × √(area / n)，紧凑度系数 0.8 确保布局在可用空间内自然收束 - 降温：乘法降温 200 次迭代，末温 ≈ 初温 1%
- 软边界：边距 8% 画布短边，越界时 80% 温和拉回，避免硬钳制导致顶点共线
- 小图增强：≤4 顶点的分量理想间距放大 1.2 倍
- 确定性：固定随机种子 42，相同图产生相同布局
name（string）：内部唯一标识（如A或A#1）display_name（string）：画布显示名（如A），支持同名不同实例id（int）：自增编号
from/to（string）：端点名weight（double）：权重，默认 1.0directed（bool）：false = 无向，true = 有向id（int）：全局唯一，平行边各不同；无向反向边共享同一 idexplicit_weight（bool）：用户是否显式提供权重；决定全局权重显示策略
- 邻接表
adj_：unordered_map<string, vector<Edge>> - 无向边双向存储（反向边共享 id），有向边单向存储
- 自环仅存储一次
- 孤立点存储为
adj_[name] = {}（空邻接表），通过degree(name) == 0判定 getAllEdges()按 id 去重，平行边各自保留
手动字符扫描（非纯正则），6 阶段结构化解析（v1.2.2 严格化）：
- 预处理：
#截断注释，去除首尾空白 - 顶点解析：
"..."引号模式支持转义\"和\\；无引号名遇-<>即停 - 孤立点检测：若左顶点后无操作符（行尾/仅剩空白），创建孤立点
- 操作符解析（x-W-y 结构）：
- 收集
[-\d.<>]+ 引号子串 - 末尾数字裁剪（防止贪吃右顶点）
- 识别可选权重 W（浮点数或引号字符串；非法值报错）
- W 缺失：x+y 合计 ≥ 1 个
- - W 存在：x、y 各自 ≥ 1 个
- <仅限 x 最左、>仅限 y 最右，各至多一次
- 收集
- 方向判定：
<→ 反向有向，>→ 正向有向，同有 → 无向，皆无 → 无向 - 尾部校验：右顶点解析后行尾不得有非空白内容
- 错误上报：行号 + 具体原因，不中断其余行解析
MIT