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

函数简介

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

接口名称

GetMinimumArborescence

DLL调用

long GetMinimumArborescence(long instance, long graphPtr, string root);

参数说明

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

示例

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

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

// 获取以A为根的最小树形图
int64_t mstPtr = GetMinimumArborescence(instance, graphPtr, "A");

if (mstPtr != 0) {
    printf("最小树形图信息:\n%s\n", (char*)mstPtr);
    // 释放返回的字符串内存
    FreeStringPtr(mstPtr);
} else {
    printf("无法生成最小树形图\n");
}

// 释放资源
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}
  ]
}

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

注意事项

  • 返回的字符串指针需要调用FreeStringPtr释放内存
  • 最小树形图要求从根节点能够到达所有其他节点
  • 如果根节点无法到达某些节点，函数返回0
  • 最小树形图包含n-1条边（n为节点数）
  • 算法会考虑边的权重，选择总权重最小的有向树
  • 适用于网络设计、依赖关系分析等需要最小成本有向连接的场景
  • 对于有向图，最小树形图可能不唯一
  • 返回的字符串格式为"起点->终点(权重)"的列表
Last Updated: