C++ 中的高级图算法

CXXGraph 是一个小型库，只有头文件，用于管理 Graph 及其在 C++ 中的算法。换句话说，一个“综合 C++ 图形库”。 Graph Dijkstras Shortest Path Algorithm(Dijkstra's Shortest Path) Dijkstra's Algorithm 用于查找图中从源节点到所有其他可达节点的最短路径。该算法最初假设所有节点都无法从给定的源节点到达，因此我们将所有节点的距离标记为无穷大。（无穷大）到源节点（INF / 无穷大表示无法到达）。当边权重是小整数（以参数 C 为界）时，利用这一事实的专用队列可用于加速 Dijkstra 算法。这种类型的第一个算法是 Dial 算法（Dial 1969），用于具有正整数边权重的图，它使用桶队列来获得运行时间 O(|E|+|V|C)。（来源维基百科）Buckets 0， 1, 2,..wV 依次检查，直到找到第一个非空桶。根据定义，包含在第一个非空桶中的每个节点都具有最小距离标签。在扫描过程中，这些具有最小距离标签的节点被永久标记并从桶中删除。当顶点的距离标签发生变化时，临时标记的顶点在桶中的位置会相应更新。重复该过程，直到所有顶点都被永久标记（或所有顶点的距离最终确定）。

(Breadth First Search) Breadth First Search Algorithm(广度优先搜索) 广度优先搜索，也引作BFS，是一种Graph Traversal Algorithm。时间复杂度 O(|V| + |E|) 其中 V 是顶点的数量，E 是图中的边的数量。广度优先搜索的应用是： 寻找两个顶点之间的最短路径，比如 u 和 v，有路径以边数衡量的长度（优于深度优先搜索算法） (Depth First Search) 深度优先搜索算法 (Depth First Search) 深度优先搜索，也引用为 DFS，是一种图遍历算法。时间复杂度 O(|V| + |E|) 其中 V 为顶点数，E 为图中边数。 -first search (DFS) 查找指向当前顶点的祖先的边（它包含后边）。 DFS 跳过的所有后边缘都是循环的一部分。在无向图中，节点的父节点的边不应该算作后边，但找到任何其他已经访问过的顶点将表示后边。在无向图的情况下，只需要 O(n) 时间就可以在 n 顶点图中找到一个循环，因为最多 n - 1 条边可以是树边。许多拓扑排序算法也会检测循环，因为这些是拓扑顺序存在的障碍。此外，如果有向图已被划分为强连通分量，则环仅存在于分量内而不存在于它们之间，因为环是强连通的。对于有向图，可以使用基于分布式消息的算法。这些算法依赖于这样一个想法，即一个顶点在一个循环中发送的消息将返回到自身。分布式循环检测算法对于在计算机集群（或超级计算机）上使用分布式图处理系统处理大规模图很有用。循环检测的应用包括使用等待图来检测并发系统中的死锁。

顶点切割分区将图的边划分为相等大小的分区。保存边端点的顶点也与边本身放在同一分区中。但是，顶点在分区之间不是唯一的，并且可能必须复制（剪切），因为它们的边分布在不同的分区上。复制因子量化了与原始输入图的顶点数量相比，在计算机上复制的顶点数量。该算法是循环方式的简单顶点切割。它采用原始图边并将它们分配给分区，将其划分为相等（或相似）大小。该算法不考虑顶点复制（复制因子）中的优化，而只平衡分区中的边。所需的最低 C++ 标准是 C++17 和大于 7.3.0 的 G++ 编译器版本。库的使用很简单，把头文件放到需要的地方就行了！ git clone https://github.com/google/googletest.gitcd googletest # 克隆仓库的主目录.mkdir build # 创建一个目录来保存构建 output.cd buildcmake .. # 为 GoogleTest.makesudo make 生成原生构建脚本install # 默认安装在/usr/local/ Benchmark 需要大于3.9 的CMake 版本以及google test 和google benchmark 库。

# 查看库。$ git clone https://github.com/google/benchmark.git# Benchmark 需要 Google Test 作为依赖项。将源代码树添加为子目录。$ git clone https://github.com/google/googletest.git benchmark/googletest# 转到库根目录$ cd benchmark# 创建一个构建目录以放置构建输出。$ cmake -E make_directory "build"# 使用 cmake 生成构建系统文件。$ cmake -E chdir "build" cmake -DCMAKE_BUILD_TYPE=Release ../# 或者，从 CMake 3.13 开始，使用更简单的形式：# cmake -DCMAKE_BUILD_TYPE=Release - 。 -B "build"#构建库$ cmake --build "build" --config Release# install library$ sudo cmake --build "build" --config Release --target install 编译完成后，可以运行位于“build”目录下的名为“test_exe”的可执行文件，带有简单的命令 ./test_exe。如果您想提供支持，您可以创建拉取请求或报告问题。如果您想更改代码、修复问题或实施新功能，请阅读我们的贡献指南我们正在寻找开发人员和提交者，也是首先经验，我们将一步步引导您走向开源世界！如果您有兴趣，请通过 [email protected] 与我们联系或为此项目做出贡献。我们正在等你！