OLA 文档中心

主题

2026-06-18

获取有向图最小生成树 - GetMinimumArborescence ​

函数简介 ​

在指定的有向图中计算最小树形图（Minimum Arborescence），使用Edmonds算法实现，从根节点出发能够到达所有其他节点的有向树，其总权重最小。

接口名称 ​

GetMinimumArborescence

DLL调用 ​

c
long GetMinimumArborescence(long instance, long graphPtr, char* root);

参数说明 ​

参数名类型说明
instance长整数型OLAPlug对象的指针，由 CreateCOLAPlugInterFace 接口生成。
graphPtr长整数型图的指针，由 CreateGraph 接口返回。
root字符串根节点名称。

示例 ​

SDK 调用 ​

cpp
#include "OLAPlugServer.h"

OLAPlugServer ola;
long graphPtr = ola.CreateGraph("[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]");
if (graphPtr != 0) {
    std::string tree = ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr);
}
csharp
using OLAPlug;

var ola = new OLAPlugServer();
long graphPtr = ola.CreateGraph(@"[{"directed":false,"from":"上海","to":"北京","weight":3.0},{"directed":false,"from":"北京","to":"深圳","weight":5.0}]");
if (graphPtr != 0)
{
    string tree = ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr);
}
python
from OLAPlugServer import OLAPlugServer

ola = OLAPlugServer()
graph_ptr = ola.CreateGraph(r'[{"directed":false,"from":"上海","to":"北京","weight":3.0},{"directed":false,"from":"北京","to":"深圳","weight":5.0}]')
if graph_ptr != 0:
    tree = ola.GetMinimumArborescence(graph_ptr, "上海")
    ola.DeleteGraph(graph_ptr)
java
import com.olaplug.OLAPlugServer;

OLAPlugServer ola = new OLAPlugServer();
long graphPtr = ola.CreateGraph("[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]");
if (graphPtr != 0) {
    ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr);
}
cpp
var ola = com("OlaPlug.OlaSoft")
var graphPtr = ola.CreateGraph("[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]")
if(graphPtr) {
    ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr)
}
vbscript
Set ola = CreateObject("OlaPlug.OlaSoft")
graphPtr = ola.CreateGraph("[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]")
If graphPtr <> 0 Then
    ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr)
End If
text
.局部变量 ola, OLAPlug
ola.创建 ()
graphPtr ＝ ola.CreateGraph (“[{\“directed\“:false,\“from\“:\“上海\“,\“to\“:\“北京\“,\“weight\“:3.0},{\“directed\“:false,\“from\“:\“北京\“,\“to\“:\“深圳\“,\“weight\“:5.0}]“)
.如果真 (graphPtr ≠ 0)
    ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph (graphPtr)
.如果真结束
aardio
import OLAPlugServer;
var ola = OLAPlugServer();
var graphPtr = ola.CreateGraph("[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]");
if(graphPtr){
    ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr);
}
text
变量 ola <类型 = OLAPlugServer>
ola = 新建 OLAPlugServer
长整数 graphPtr = ola.CreateGraph("[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]")
如果真 (graphPtr ≠ 0)
{
    ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr)
}
cpp
#include "OLAPlugServer.h"

OLAPlugServer ola;
long graphPtr = ola.CreateGraph("[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]");
if (graphPtr != 0) {
    ola.GetMinimumArborescence(graphPtr, "上海");
    ola.DeleteGraph(graphPtr);
}

原生 DLL 调用 ​

cpp
long instance = CreateCOLAPlugInterFace();
long graphPtr = CreateGraph(instance, "[{\"directed\":false,\"from\":\"上海\",\"to\":\"北京\",\"weight\":3.0},{\"directed\":false,\"from\":\"北京\",\"to\":\"深圳\",\"weight\":5.0}]");
if (graphPtr != 0) {
    std::string tree = ola.GetMinimumArborescence(graphPtr, "上海");
    DeleteGraph(instance, graphPtr);
}
csharp
using System.Runtime.InteropServices;

[DllImport("OLAPlug_x64.dll", CallingConvention = CallingConvention.StdCall)]
static extern long CreateCOLAPlugInterFace();

long instance = CreateCOLAPlugInterFace();
long graphPtr = CreateGraph(instance, @"[{"directed":false,"from":"上海","to":"北京","weight":3.0},{"directed":false,"from":"北京","to":"深圳","weight":5.0}]");
if (graphPtr != 0) {
    string tree = ola.GetMinimumArborescence(graphPtr, "上海");
    DeleteGraph(instance, graphPtr);
}
python
from ctypes import CDLL, c_int, c_int64

ola = CDLL("OLAPlug_x64.dll")
ola.CreateCOLAPlugInterFace.restype = c_int64
instance = ola.CreateCOLAPlugInterFace()
graph_ptr = ola.CreateGraph(instance, b'[{"directed":false,"from":"上海","to":"北京","weight":3.0},{"directed":false,"from":"北京","to":"深圳","weight":5.0}]')
if graph_ptr:
    tree = ola.GetMinimumArborescence(graph_ptr, "上海")
    ola.DeleteGraph(instance, graph_ptr)

返回值 ​

返回值说明
（返回值）返回最小树形图信息的字符串指针，格式为JSON：。
json
{
  "totalWeight": 9.0,
  "edges": [
    {"from": "A", "to": "C", "weight": 2.0},
    {"from": "B", "to": "C", "weight": 1.0},
    {"from": "D", "to": "E", "weight": 2.0},
    {"from": "A", "to": "B", "weight": 4.0}
  ]
}
字段名类型说明
totalWeight浮点数totalWeight 字段值。
edges数组edges 结果列表，详见下方字段说明。

如果无法生成最小树形图返回0。

返回的字符串指针需要调用 FreeStringPtr 释放内存。

edges 元素字段说明：

字段名类型说明
from字符串from 字段。
to字符串to 字段。
weight浮点数weight 字段。

注意事项 ​

项目说明
最小树形图要求从根节点能够到达所有其他节点最小树形图要求从根节点能够到达所有其他节点，否则返回0。
最小树形图包含 n-1 条边（n为节点数）最小树形图包含 n-1 条边（n为节点数）。