获取最小生成树 - GetMinimumSpanningTree

函数简介

在指定的图中计算最小生成树，连接图中所有节点且总权重最小。

接口名称

GetMinimumSpanningTree

DLL调用

long GetMinimumSpanningTree(long instance, long graphPtr);

参数说明

参数名	类型	说明
instance	长整数型	OLAPlug对象的指针，由 CreateCOLAPlugInterFace 接口生成。
graphPtr	长整数型	图的指针，由 CreateGraph 接口返回

示例

// 创建OLA实例
int64_t instance = CreateCOLAPlugInterFace();

// 创建图并添加边
int64_t graphPtr = CreateGraph(instance, "");
AddEdge(instance, graphPtr, "A", "B", 4.0, false);
AddEdge(instance, graphPtr, "A", "C", 2.0, false);
AddEdge(instance, graphPtr, "B", "C", 1.0, false);
AddEdge(instance, graphPtr, "B", "D", 5.0, false);
AddEdge(instance, graphPtr, "D", "E", 2.0, false);

// 获取最小生成树
int64_t mstPtr = GetMinimumSpanningTree(instance, graphPtr);

if (mstPtr != 0) {
    printf("%s\n", (char*)mstPtr);
    FreeStringPtr(mstPtr);
}

// 释放资源
DeleteGraph(instance, graphPtr);
DestroyCOLAPlugInterFace(instance);

返回值

返回最小生成树信息的字符串指针，格式为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为节点数）。