3 Star 6 Fork 0

Koala999 / kGraph

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
贡献代码
同步代码
取消
提示: 由于 Git 不支持空文件夾,创建文件夹后会生成空的 .keep 文件
Loading...
README
MIT

kGraph

介绍

基于C++模板实现的图基本算法

核心代码参考Algorithms in C++ Part 5: Graph Algorithms, Robert Sedgewick, 3rd Edition.

代码结构

base\,基础支持数据结构和算法

core\,核心图算法

util\,一些实用函数

test\,测试代码

GraphX.h,定义了一些基础的图类型

图结构

图的结构布局与算法相对独立实现。

纵向上有稠密图、稀疏图、扁平图3类基本结构;

横向上有无向/有向、单边/多边、始终排序3类配置参数。

两者结合可构造丰富多样的底层结构。

图算法

  1. 邻接顶点迭代器
  2. 深度优先(Dfs)、广度优先(Bfs)和基于优先队列(Pfs)的迭代器
  3. 连通、强连通检测
  4. 二分图检测
  5. 桥、割点检测
  6. 拓扑排序:基于源点队列, 基于Dfs的逆排序
  7. 传递闭包:Warshall, Dfs, Dag-Dfs, Strongly-Connected
  8. 最小生成树:Prim, Kruskal, Boruvka, Pfs
  9. 最优路径:单源(Dijkstra, Pfs, TS, Bellman-Ford),全源(Dijkstra, Pfs, Dfs, Floyd)
  10. 最大流:Path-Augment, Pfs, Edmonds-Karp/Bfs, Preflow

编译

编译器须支持c++17。核心代码全C++模板实现,不需编译,测试代码通过MSVC2019和GCC11编译。

使用说明

创建有向稠密图的示例代码:

    #include "GraphX.h"

    DigraphDd g(6);
    g.addEdge(0, 1, 0.41), g.addEdge(0, 5, 0.29); 
    g.addEdge(1, 2, 0.51), g.addEdge(1, 4, 0.32); 
    g.addEdge(2, 3, 0.50);
    g.addEdge(3, 0, 0.45), g.addEdge(3, 5, 0.38);
    g.addEdge(4, 2, 0.32), g.addEdge(4, 3, 0.36);
    g.addEdge(5, 1, 0.29), g.addEdge(5, 4, 0.20);

对图g进行深度优先迭代的示例代码:

    #include "../core/KtDfsIter.h"

    KtDfsIter<DigraphDd> dfs(g, 0);
    std::vector<unsigned> v;
    for (; !dfs.isEnd(); ++dfs) 
        v.push_back(*dfs); // *dfs表示当前遍历的顶点序号

更多示例代码参考test目录下的测试代码。

MIT License Copyright (c) 2021 Koala999 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

简介

图论基本算法 basic graph algorithm library 展开 收起
C++ 等 2 种语言
MIT
取消

发行版 (7)

全部

贡献者

全部

近期动态

加载更多
不能加载更多了
C++
1
https://gitee.com/koala999/kgl.git
git@gitee.com:koala999/kgl.git
koala999
kgl
kGraph
master

搜索帮助

14c37bed 8189591 565d56ea 8189591