修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

v5.0
搜索
    v5.0

      拓扑排序

      ✓ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

      概述

      有向图的拓扑排序(Topological Sort)是指将图中的节点按照一定的顺序进行排列,使得每条边的起点在终点之前。需要注意的是,拓扑排序仅适用于有向无环图(DAG)。

      拓扑排序在计算机科学和其他领域有着各种应用。在项目管理和作业调度中,拓扑排序能够根据任务之间的依赖关系确定任务执行的最佳顺序。它还可用于解决软件开发中模块、库或组件之间的依赖关系。这一算法可以按照正确的顺序解决依赖关系,减少冲突和潜在错误的发生。

      基本概念

      有向无环图(DAG)

      有向无环图(Directed Acyclic Graph, DAG)是指不存在有向环路(Cycle)的有向图。换句话说,在DAG中无法从任意一个节点v出发,经过一条有向路径后又回到节点v。

      如下所示,第一个和第二个图是DAG,而第三个图中包含一个有向循环(B→C→D→B),不符合DAG的定义。

      是否可以进行拓扑排序常作为判断一个有向图是否为DAG的标准。

      拓扑排序

      每个DAG至少有一种拓扑排序。

      在上述示例中,第一个图中的节点有3种可能的排序:

      • A, E, B, D, C
      • A, B, E, D, C
      • A, B, D, E, C

      当DAG中存在包含所有节点的有向路径时,DAG才具有唯一的拓扑排序,此时排序与路径中节点出现的顺序相同。

      在下面的示例中,图中的节点只有1种可能的排序:A, B, D, C, E, F。

      特殊说明

      在存在环路的图上运行拓扑排序算法将导致一些节点在排序中被忽略掉,被忽略的节点包括:

      • 环路(包括自环)中的节点;
      • 环路中的节点通过出边能触达的其他节点。

      在以下的示例中,首先忽略环路中的节点C、D和G,其次忽略从环路节点出边可达的其他节点,包括节点F、J和H。下图拓扑排序结果为:A, I, B, E。

      如果一个图是非连通的,或是因为忽略上述构成环路和受环路影响的节点后变成非连通,拓扑排序会分别在每个连通分量内进行,并统一返回排序结果。孤点也不会被忽略。

      语法

      • 命令:algo(topological_sort)
      • 本算法无参数

      示例

      示例图如下:

      文件回写

      配置项 回写内容
      filename _id,_id,...
      algo(topological_sort).params().write({
         file: {
             filename: 'sort'
         }
      })
      

      结果:文件sort

      H
      F
      A
      B
      C
      D
      E
      G
      

      直接返回

      别名序号
      类型
      描述
      0 []nodes 排序后的节点数组
      algo(topological_sort).params() as nodes
      return nodes
      

      结果:nodes

      8
      6
      1
      2
      3
      4
      5
      7

      流式返回

      别名序号
      类型
      描述
      0 []nodes 排序后的节点数组
      algo(topological_sort).params().stream() as n
      find().nodes(n) as nodes
      return nodes{*}
      

      结果:nodes

      _id _uuid
      H 8
      F 6
      A 1
      B 2
      C 3
      D 4
      E 5
      G 7
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写