| sidebar_position | 1 |
|---|
算子类别：Basics（图结构判定、基础遍历与结构合法性校验）
算法数量：15 个
适用阶段：图合法性校验、结构诊断、依赖分析、层级/上下游分析、遍历与排序、图结构匹配、平面性分析、特殊图类型识别
产品定位：为“这个图是否合法 / 是否有环 / 是否能排序 / 上下游是谁 / 怎么遍历 / 两个图结构是否一致 / 是否满足特殊图结构”提供基础算子能力底座。
Basics 算子集聚焦于图的基础结构性质判断、基础遍历/排序能力以及特殊图结构识别，主要回答以下问题：
-
结构合法性
- 是不是树 / 森林 / DAG？
- 是否存在环？
- 是否满足平面图、竞赛图等特殊结构？
-
依赖与层级关系
- 一个节点的上游是谁？（ancestors）
- 一个节点的下游是谁？（descendants）
- 是否可以按照依赖关系进行排序？
-
遍历与生成结构
- 从某个节点出发如何层层扩散？（BFS）
- 如何深入探索一条关系链？（DFS）
-
依赖排序问题
- 是否可以拓扑排序？
- 有哪些可行的执行顺序？
- 在多种可行顺序下如何稳定排序？
-
结构相似与特殊图识别
- 两个图是否结构等价？（is_isomorphic）
- 图是否为 AT-free 图？
- 图是否可以平面嵌入？（check_planarity）
- 有向图是否为竞赛图？（is_tournament）
- 给定分数序列是否可构造为竞赛图？（score_sequence）
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 树/森林判定 | is_tree, is_forest |
判断图是否满足树或森林结构 |
| DAG 判定 | is_directed_acyclic_graph |
判断有向图是否为有向无环图 |
| 基础遍历（广度） | bfs_tree |
从起点构建 BFS 分层遍历树 |
| 基础遍历（深度） | dfs_tree |
从起点构建 DFS 深度遍历树 |
| 拓扑排序 | topological_sort |
输出一种合法的拓扑排序结果 |
| 稳定拓扑排序 | lexicographical_topological_sort |
输出按字典序约束的稳定拓扑序 |
| 拓扑全枚举 | all_topological_sorts |
枚举 DAG 中所有合法拓扑序 |
| 上游分析 | ancestors |
查询指定节点的所有祖先节点 |
| 下游分析 | descendants |
查询指定节点的所有后继节点 |
| 图同构判定 | is_isomorphic |
判断两个图是否具有相同结构 |
| AT-free 图判定 | is_at_free |
判断图是否为 AT-free 图 |
| 平面性检测 | check_planarity |
判断图是否可以在平面上无交叉绘制 |
| 竞赛图判定 | is_tournament |
判断有向图是否为竞赛图 |
| 竞赛图分数序列 | score_sequence |
计算竞赛图中各节点的出度分数序列 |
- 输入
G：NetworkX Graph / DiGraph - 常见输出类型：
- 判定类：
bool - 集合类：
set(node) - 遍历类：
NetworkX DiGraph（生成树） - 排序类：
list/iterator - 结构类：图嵌入对象、序列或匹配判断结果
- 判定类：
功能说明
判断无向图是否满足“连通 + 无环”的树定义。
产品价值
- 快速校验层级结构是否合法
- 防止隐含循环或结构断裂
- 适合作为树形数据建模前置校验
典型场景
- 组织架构校验
- 任务依赖树校验
- 物料 / 装配层级校验
- 家族关系或分类体系校验
适用与特性
- 图类型：无向图
- 复杂度：
O(V + E)
功能说明
判断无向图是否由多棵互不相连的树组成。
产品价值
- 验证多个独立层级结构是否合法
- 检查是否存在跨组件循环
- 适合多子系统、多组织、多链路结构分析
典型场景
- 多部门组织结构
- 多产品线装配关系
- 多条独立资金链分析
- 多棵分类树合法性校验
适用与特性
- 图类型：无向图
- 复杂度：
O(V + E)
功能说明
判断有向图是否为有向无环图（DAG）。
产品价值
- 拓扑排序、关键路径、依赖调度等算法的前置校验
- 识别循环依赖风险
- 判断流程、任务、引用关系是否可线性展开
典型场景
- 项目任务依赖
- 编译 / 构建依赖
- 数据血缘分析
- 审批与流程系统
- 调用链与引用链分析
适用与特性
- 图类型：有向图
- 复杂度：
O(V + E)
功能说明
从指定节点出发，按层级顺序构建 BFS 遍历树。
产品价值
- 天然形成“距离起点几跳”的层级结构
- 适合展示扩散范围和层级关系
- 对最短跳数关系具有较强解释性
典型场景
- 社交圈层扩散
- 组织层级展示
- 城市 / 站点分层可达分析
- 风险传播的层级影响范围分析
关键参数
source：起点节点depth_limit：最大遍历层数
适用与特性
- 图类型：有向图 / 无向图
- 复杂度：
O(V + E)
功能说明
从指定节点出发，沿一条路径尽可能深入，构建 DFS 遍历树。
产品价值
- 适合路径挖掘与链式关系分析
- 便于发现深层依赖、深层关系和长链结构
- 常用于搜索、回溯和结构探查
典型场景
- 调用链分析
- 文件 / 目录扫描
- 深度调查关系链
- 深层依赖追踪
- 图结构探索
适用与特性
- 图类型：有向图 / 无向图
- 复杂度：
O(V + E)
功能说明
在 DAG 中生成一种满足依赖约束的线性顺序。
产品价值
- 给出“可执行顺序”的一种解
- 是调度、构建、流程编排的基础能力
- 可用于将复杂依赖图转化为线性执行序列
典型场景
- 项目任务排序
- 构建系统
- 审批流程
- 数据处理流水线
- 课程先修关系排序
适用与特性
- 图类型：有向无环图（DAG）
- 复杂度：
O(V + E)
功能说明
在所有可行拓扑序中，按照指定的字典序规则输出稳定的拓扑排序结果。
产品价值
- 输出结果稳定、可复现
- 适合产品化展示和自动化流程
- 避免同一图多次计算产生不同排序结果
典型场景
- 编译 / 构建顺序
- 页面生成顺序
- 审批编号排序
- 多任务调度中的稳定排序
- 测试用例执行顺序生成
适用与特性
- 图类型：有向无环图（DAG）
- 复杂度：
O(E + V log V)
功能说明
枚举 DAG 中所有可能的合法拓扑排序结果。
产品价值
- 探索所有可行执行方案
- 用于方案枚举、决策分析和路径比较
- 帮助识别依赖约束下的调度灵活性
典型场景
- 项目排期多方案分析
- 多审批路径探索
- 多调度方案比较
- 任务执行顺序优化
- 小规模依赖图穷举分析
注意事项
- 结果数量可能呈指数级增长
- 更适合小规模 DAG
- 大图场景建议使用单一拓扑排序或稳定拓扑排序
功能说明
返回所有可以到达指定节点的上游节点集合。
产品价值
- 快速定位“谁影响了我”
- 适合溯源、责任链、引用来源分析
- 可用于依赖风险和影响来源识别
典型场景
- 资金来源追溯
- 数据血缘上游分析
- 引用链分析
- 管理汇报链查询
- 任务依赖来源分析
适用与特性
- 图类型：有向图
- 输出：
set(node) - 复杂度：
O(V + E)
功能说明
返回从指定节点出发可达的所有下游节点集合。
产品价值
- 衡量一个节点的影响范围
- 支持传播分析、依赖影响评估和风险扩散分析
- 快速回答“我会影响谁”
典型场景
- 舆情 / 信息扩散
- 任务延期影响评估
- 资金流向分析
- 服务调用影响面分析
- 数据血缘下游分析
适用与特性
- 图类型：有向图
- 输出：
set(node) - 复杂度：
O(V + E)
功能说明
判断两个图是否在结构上等价，即是否可以通过节点重命名使两个图完全一致。
产品价值
- 识别结构相同但节点命名不同的图
- 支持模板匹配、模式识别和重复结构发现
- 可用于图结构去重与相似结构归并
典型场景
- 流程模板匹配
- 网络结构去重
- 欺诈团伙结构识别
- 分子结构比较
- 子系统拓扑结构一致性校验
适用与特性
- 图类型：有向图 / 无向图
- 输出：
bool - 注意：图同构问题计算成本较高，大规模图需谨慎使用
功能说明
判断图是否为 AT-free 图，即图中是否不存在 asteroidal triple（三点之间满足特定避开邻域路径关系的结构）。
产品价值
- 用于识别具有特殊结构性质的图
- 支持图论结构分析和特殊图类建模
- 可作为部分高级图算法或图分解任务的前置判断
典型场景
- 特殊图类识别
- 图结构理论分析
- 区间图、弦图等相关结构研究
- 网络结构约束校验
适用与特性
- 图类型：通常用于无向图
- 输出：
bool - 适合结构诊断、特殊图识别和算法前置筛选
功能说明
判断图是否为平面图，即是否可以将图绘制在平面上且边之间不发生交叉。
产品价值
- 判断网络是否适合平面化布局
- 支持拓扑可视化、线路规划和结构简化
- 可用于发现复杂交叉关系和布局瓶颈
典型场景
- 网络拓扑可视化
- 电路图 / 管线图结构校验
- 路网与空间网络分析
- 图布局优化
- 平面嵌入分析
常见输出
- 是否平面：
bool - 平面嵌入结构：planar embedding
适用与特性
- 图类型：通常用于无向图
- 复杂度：通常为线性级别
O(V + E)
功能说明
判断有向图是否为竞赛图。竞赛图要求任意两个不同节点之间都存在且仅存在一条有向边。
产品价值
- 适合处理两两比较、胜负关系、偏好关系等场景
- 可判断成对竞争关系是否完整
- 支持排序、排名和竞争结构分析
典型场景
- 赛事胜负关系分析
- 两两偏好比较
- 排名系统校验
- 决策偏好图分析
- 成对 PK 关系建模
适用与特性
- 图类型：有向图
- 输出：
bool - 要求节点之间的两两关系完整且方向唯一
功能说明
计算竞赛图中每个节点的分数序列，通常对应节点在竞赛图中的出度序列。
产品价值
- 用于刻画竞赛图中节点的胜负能力分布
- 支持排名、强弱分析和整体竞争格局判断
- 可与竞赛图判定结合，用于两两比较网络分析
典型场景
- 比赛结果统计
- 排名系统分析
- 偏好关系强度分析
- 节点竞争力评估
- 竞赛图结构摘要
适用与特性
- 图类型：竞赛图 / 有向图
- 输出：分数序列
- 常与
is_tournament搭配使用
- 判断是否为树：
is_tree - 判断是否为森林：
is_forest - 判断是否为 DAG：
is_directed_acyclic_graph - 判断是否为平面图：
check_planarity - 判断是否为竞赛图：
is_tournament - 判断是否为 AT-free 图：
is_at_free
- 查询上游节点：
ancestors - 查询下游节点：
descendants - 判断是否可排序：
is_directed_acyclic_graph - 生成执行顺序：
topological_sort
- 分层扩散分析：
bfs_tree - 深层链路分析：
dfs_tree
- 给出一种执行顺序：
topological_sort - 给出稳定执行顺序：
lexicographical_topological_sort - 枚举所有执行顺序：
all_topological_sorts
- 判断两个图结构是否一致：
is_isomorphic - 判断图是否可平面绘制：
check_planarity - 判断是否为竞赛图：
is_tournament - 获取竞赛图分数序列：
score_sequence
- “这个依赖图是不是 DAG？”
- “这个组织结构是不是一棵树？”
- “这个图是不是森林结构？”
- “某个任务延期会影响哪些下游任务？”
- “列出某节点的所有上游来源。”
- “从这个节点开始，按层级展开有哪些节点？”
- “从这个节点开始，沿关系链深挖会经过哪些节点？”
- “给出一个合理的执行顺序。”
- “按编号最小优先给我一个稳定执行顺序。”
- “一共有多少种合法的执行方案？”
- “这两个图的结构是不是一样？”
- “这个网络能不能画成没有边交叉的平面图？”
- “这个有向图是不是竞赛图？”
- “这个竞赛图中各节点的胜负分数是多少？”
- “这个图是否属于 AT-free 图？”
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | is_tree |
判断图是否为树 |
| 2 | is_forest |
判断图是否为森林 |
| 3 | is_directed_acyclic_graph |
判断图是否为有向无环图 |
| 4 | bfs_tree |
构建广度优先遍历树 |
| 5 | dfs_tree |
构建深度优先遍历树 |
| 6 | topological_sort |
拓扑排序 |
| 7 | lexicographical_topological_sort |
字典序拓扑排序 |
| 8 | all_topological_sorts |
枚举所有拓扑排序 |
| 9 | ancestors |
查询上游祖先节点 |
| 10 | descendants |
查询下游后继节点 |
| 11 | is_isomorphic |
判断两个图是否同构 |
| 12 | is_at_free |
判断图是否为 AT-free 图 |
| 13 | check_planarity |
检测图是否为平面图 |
| 14 | is_tournament |
判断图是否为竞赛图 |
| 15 | score_sequence |
计算竞赛图分数序列 |