任何人都可以指出正确的数据结构/算法来完成以下任务吗?
我想合并(合并?)以下两组节点以获得第三组节点。
谢谢!
最佳答案
简答
- 联合节点集。
- 合并边集。
长答案
我假设您使用的是图形数据结构,其中有 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
关于algorithm - 两个网络图的并集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22207688/