# Graph

**Repository Path**: cantour123/graph

## Basic Information

- **Project Name**: Graph
- **Description**: 创建图数据结构的仓库，实现一些基础图算法.
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-02-27
- **Last Updated**: 2025-03-03

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## Graph项目的介绍

此项目的目的是参考Python的NetworkX库，实现一个C++的类库用于处理于图有关的数据结构。

核心的类有两个，Graph(有向图)和UnDirGraph(无向图)，后者继承前者。*ps:作者在阅读NetworkX库的源码时，看到该库的实现方式是有向图和无向图都继承于一个基类，但是我目前没有看到这种设计方式的好处。*

下面详细介绍Graph类的结构，它有一个核心数据结构map<V,map<V,E>> m_data是一个二级map结构，其中V表示节点类型,E表示边的类型(要求节点类型是有序的，边的类型可以进行加减运算)，还有一个数据是 m_empty,它的含义是边的默认值。ps:作者在阅读NetworkX库的源码时，看到该库的实现方式是对边再封装一层，即map<V,map<V,map<string,E>>>,这样的好处是可以表达更丰富关于边的信息，也就是如果是无权图，则最里面一层的map<string,E>为空，这样可以不用额外引入变量m_empty，同时再处理如最大流问题，可以将权重"weight"变为字符串"capacity"，未来会参考这一优秀的设计。

接着介绍Graph类实现的方法，算法实现的包括BFS，DFS，Dijkstra，Floyd，Belleman_Ford，Ford_Fulkerson。其中最优匹配算法(Hungarian算法实现方式为暴力枚举，因此计算效率比较低)。辅助的算法包括，添加节点，添加边，获取当前图中的节点，判断两个节点之间是否连通，判断整个图是否连通，判断整个图是不是DGA，在路径上减去一个值(当减到0时自动删除这条边)，将有向图转化为无向图。以及一些用于测试的函数，包括print(),Draw(),write2Dot.其中write2Dot是用来做图的可视化操作，将图转化为.dot格式，利用dot工具将图画出来。

UnDirGraph类的设计与Graph类似，其中需要额外注意的是无向图在引入边的过程中需要添加两条边，在输出的过程中需要去重。它实现的算法有最小生成树算法，包括两个算法，prim算法和Kruskal算法。

以上的算法全部全部经过测试，测试方法是在调用Python的NetworkX库生成1000个样本，利用该库给出需要测试算法的结果。C++读取样本与结果，然后与此项目算法的结果进行比较，结果全部正确。