修改密码

请输入密码
请输入密码 请输入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

      最小生成树

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

      概述

      最小生成树(Minimum Spanning Tree, MST)算法计算图中每个连通分量的边权重之和最小的生成树。

      MST在网络设计、聚类和优化等问题中具有各种应用,其中最小化总成本或权重是重要的目标。

      基本概念

      生成树

      一个生成树(Spanning Tree)是一个连通图G = (V, E)(或一个连通分量)的连通子图,它包含图中的所有节点,并形成一个树结构(即无环)。一个图可能存在多个生成树,而每个生成树必定有(|V| - 1)条边。

      下图中的11个节点和10条用红色突出显示的边构成该图的一个生成树:

      最小生成树(MST)

      最小生成树(MST)是边权重和最小的生成树。MST的构建从给定的起点开始。起点的选择不会影响MST算法的正确性,但会影响MST的结构和边的添加顺序。不同的起点可能产生不同的MST,但对于给定的图,它们都是有效的MST。

      给上面的示例图赋予边权重后,使用不同起点产生的三个可能的MST在下面以红色突出显示:

      关于起点的选择:

      • 每个连通分量只需要一个起点。如果指定了多个起点,只有第一个有效。
      • 如果某个连通分量没有指定起点,则不会为其计算MST。
      • 孤点不是计算MST的有效起点。

      特殊说明

      • 最小生成树算法忽略边的方向,按照无向边进行计算。

      语法

      • 命令:algo(mst)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      ids / uuids []_id / []_uuid / / 起点的ID/UUID;如果忽略,系统将为每个连通分量选择一个起点
      edge_schema_property []@<schema>?.<property> 数值类型,需LTE / 用作边权重的属性,权重值为所有指定属性值中的最小值;没有任何指定属性的边不参与构成MST
      limit int ≥-1 -1 返回的结果条数,-1返回所有结果

      示例

      示例图如下,节点A是电力中心,节点B~H是周围的村庄。每条边上标有其UUID和连接位置之间的距离,表示所需的电缆长度:

      文件回写

      配置项
      回写内容
      描述
      filename _id--[_uuid]--_id MST中的一步路径:(起点)--(边)--(终点)
      algo(mst).params({
        uuids: [1],
        edge_schema_property: 'distance'
      }).write({
        file:{
          filename: 'solution'
          }
      })
      

      结果:文件solution

      A--[107]--H
      A--[108]--E
      E--[111]--G
      F--[113]--G
      A--[101]--B
      A--[104]--D
      C--[103]--D
      

      直接返回

      别名序号
      类型
      描述
      0 []path MST中的一步路径:_uuid (起点) -- [_uuid] (边) -- _uuid (终点)
      algo(mst).params({
        ids: 'A',
        edge_schema_property: '@connect.distance'
      }) as mst 
      return mst
      

      结果:mst

      1--[107]--8
      1--[108]--5
      5--[111]--7
      6--[113]--7
      1--[101]--2
      1--[104]--4
      3--[103]--4

      流式返回

      别名序号
      类型
      描述
      0 []path MST中的一步路径:_uuid (起点) -- [_uuid] (边) -- _uuid (终点)
      algo(mst).params({
        uuids: [1],
        edge_schema_property: 'distance'
      }).stream() as mst
      with pedges(mst) as mstUUID
      find().edges(mstUUID) as edges
      return sum(edges.distance)
      

      结果:5.65

      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写