联合的两个网络图

Question

有人能指出我正确的数据结构/算法来完成以下任务吗？

我想结合(Union？)以下两组节点来获得第三组.

谢谢!

Answer 1

简短回答

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

长答案

我假设您使用的是图形数据结构，其中存在Node实例，每个实例Node都有 astring Name和 a list<Node> Next。

我们将这两个图称为G和H，其中一个图是 a list<Node>。

令GNames和HNames为每个图中的节点名称集。让是和MNames的并集。GNamesHNames

创建一个新图表，其中中的每个名称list<Node> M都有一个新图表。NodeMNames

构建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)nameNextNamesMLookup[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