跳到主要内容

Basics 基础算子集

算子类别：Basics（图结构判定与基础遍历）

适用阶段：图合法性校验、结构诊断、依赖分析、层级/上下游分析、遍历与排序

产品定位：为“这个图是不是合法结构 / 是否有环 / 能否排序 / 上下游是谁 / 怎么遍历”提供基础算子能力底座

一、算子集概述​

Basics 算子集聚焦于图的基础结构性质判断与基础遍历/排序能力，主要回答以下问题：

  1. 结构合法性

    • 是不是树 / 森林 / DAG？
    • 是否存在环？

  2. 依赖与层级关系

    • 一个节点的上游是谁？（ancestors）
    • 一个节点的下游是谁？（descendants）

  3. 遍历与生成结构

    • 从某个节点出发如何层层扩散？（BFS）
    • 如何深入探索一条关系链？（DFS）

  4. 依赖排序问题

    • 是否可以拓扑排序？
    • 有哪些可行的执行顺序？
    • 在多种可行顺序下如何稳定排序？

二、算子能力分类​

能力类型对应算子功能描述
树/森林判定is_tree, is_forest判断图是否满足树或森林结构
DAG 判定is_directed_acyclic_graph判断有向图是否无环
基础遍历（广度）bfs_tree构建 BFS 分层遍历树
基础遍历（深度）dfs_tree构建 DFS 深度遍历树
拓扑排序topological_sort输出任意一种合法拓扑序
稳定拓扑排序lexicographical_topological_sort输出按字典序约束的拓扑序
拓扑全枚举all_topological_sorts枚举所有合法拓扑序
上游分析ancestors查询节点的所有祖先
下游分析descendants查询节点的所有后继

三、通用输入输出约定​

  • 输入 G：NetworkX Graph / DiGraph
  • 输出类型：
    • 判定类：bool
    • 集合类：set(node)
    • 遍历类：NetworkX DiGraph（生成树）
    • 排序类：list / iterator

四、算子详细说明​

1. is_tree —— 是否为树结构​

功能说明
判断无向图是否满足“连通 + 无环”的树定义。

产品价值

  • 快速校验层级结构是否合法
  • 防止隐含循环或多父节点问题

典型场景

  • 组织架构校验
  • 任务依赖树校验
  • 物料/装配层级校验

适用与特性

  • 图类型：无向图
  • 复杂度：O(V + E)

2. is_forest —— 是否为森林结构​

功能说明
判断无向图是否由多棵互不相连的树组成。

产品价值

  • 验证多子系统是否互相独立
  • 检查是否存在跨组件循环

典型场景

  • 多部门组织结构
  • 多产品线装配关系
  • 多条独立资金链分析

适用与特性

  • 图类型：无向图
  • 复杂度：O(V + E)

3. is_directed_acyclic_graph —— DAG 判定​

功能说明
判断有向图是否为有向无环图（DAG）。

产品价值

  • 拓扑排序、关键路径等算法的前置校验
  • 识别循环依赖风险

典型场景

  • 项目任务依赖
  • 引用 / 交易 / 调用关系
  • 审批与流程系统

适用与特性

  • 图类型：有向图
  • 复杂度：O(V + E)

4. ancestors —— 上游节点查询​

功能说明
返回所有可以到达指定节点的上游节点集合。

产品价值

  • 快速定位“谁影响了我”
  • 用于溯源、责任链、引用来源分析

典型场景

  • 资金来源追溯
  • 引用链分析
  • 管理汇报链查询

适用与特性

  • 图类型：有向图
  • 复杂度：O(V + E)

5. descendants —— 下游节点查询​

功能说明
返回从指定节点出发可达的所有下游节点集合。

产品价值

  • 衡量影响范围
  • 用于传播分析、依赖影响评估

典型场景

  • 舆情/信息扩散
  • 任务延期影响评估
  • 资金流向分析

适用与特性

  • 图类型：有向图
  • 复杂度：O(V + E)

6. bfs_tree —— 广度优先遍历树​

功能说明
从指定节点出发，按层级顺序构建 BFS 遍历树。

产品价值

  • 天然层级结构
  • 最短跳数关系可解释

典型场景

  • 社交圈层扩散
  • 组织层级展示
  • 城市/站点分层可达分析

关键参数

  • source：起点
  • depth_limit：最大层数

复杂度

  • O(V + E)

7. dfs_tree —— 深度优先遍历树​

功能说明
从指定节点出发，沿一条路径尽可能深入，构建 DFS 树。

产品价值

  • 适合路径挖掘与链式分析
  • 快速发现深层关系

典型场景

  • 调用链分析
  • 文件/目录扫描
  • 深度调查关系链

复杂度

  • O(V + E)

8. topological_sort —— 拓扑排序​

功能说明
在 DAG 中生成任意一种满足依赖约束的线性顺序。

产品价值

  • 给出“可执行顺序”的一种解
  • 调度、构建、流程编排基础能力

典型场景

  • 项目任务排序
  • 构建系统
  • 审批流程

复杂度

  • O(V + E)

9. lexicographical_topological_sort —— 字典序拓扑排序​

功能说明
在所有可行拓扑序中，选择字典序最小的一种。

产品价值

  • 结果稳定、可复现
  • 适合产品化输出与展示

典型场景

  • 编译/构建顺序
  • 页面生成顺序
  • 审批编号排序

复杂度

  • O(E + V log V)

10. all_topological_sorts —— 全拓扑序枚举​

功能说明
枚举 DAG 中所有可能的拓扑排序结果。

产品价值

  • 探索所有可行方案
  • 用于方案枚举与决策分析

典型场景

  • 项目排期多方案分析
  • 多审批路径探索
  • 多调度方案比较

注意事项

  • 结果数量可能指数级增长
  • 适合小规模 DAG

五、推荐使用指南​

  • 先校验结构：is_directed_acyclic_graph / is_tree
  • 查上下游关系：ancestors / descendants
  • 展示层级关系：bfs_tree
  • 深度路径分析：dfs_tree
  • 给出执行顺序：topological_sort
  • 需要稳定顺序：lexicographical_topological_sort
  • 需要全部方案：all_topological_sorts

六、可直接回答的典型问题​

  • “这个依赖图是不是 DAG？”
  • “某个任务延期会影响哪些下游任务？”
  • “列出某节点的所有上游来源。”
  • “给出一个合理的执行顺序。”
  • “一共有多少种合法的执行方案？”
  • “按编号最小优先给我一个执行顺序。”