algorithm - 两个网络图的并集

Question

任何人都可以指出正确的数据结构/算法来完成以下任务吗？

我想合并(合并？)以下两组节点以获得第三组节点。

谢谢!

Answer 1

简答

1. 联合节点集。
2. 合并边集。

长答案

我假设您使用的是图形数据结构，其中有 Node实例，其中每个 Node有一个 string Name和一个 list<Node> Next .

让我们称您的两个图表为 G和 H ，其中图形是 list<Node> .

让GNames和 HNames是每个图中的节点名称集。让MNames成为GNames的联盟和 HNames .

创建一个新图 list<Node> M哪里有新的 Node对于 MNames 中的每个名称.

构建 map<string, Node> GLookup, HLookup, MLookup作为从节点名称到 Node 的映射对于每个 list<Node> G, H, M .

对于每个 Node u在这张新图中M , 计算 NextNames作为GLookup[u.Name].Next.Select(v => v.Name)的联盟和 HLookup[u.Name].Next.Select(v => v.Name) , 然后对于每个名字 name在NextNames , 添加 MLookup[name]至 u.Next .

M现在是您的合并图。

伪代码

list<Node> merge(list<Node> G, list<Node> H)
    GNames = G.Select(u => u.Name)
    HNames = H.Select(u => u.Name)
    MNames = union(GNames, HNames)
    M = MNames.Select(name => new Node(name))
    GLookup = G.ToMap(u => u.Name)
    HLookup = H.ToMap(u => u.Name)
    MLookup = M.ToMap(u => u.Name)
    foreach u in M
        NextNames = union(
                        GLookup[u.Name].Next.Select(v => v.Name),
                        HLookup[u.Name].Next.Select(v => v.Name))
        foreach name in NextNames
            u.Next.Add(MLookup[name])
    return M