JavaScript过滤对象数组 移除无向网络重复双向边元素

核心思路 #

无向边的判定规则是：只要两个端点相同，不管source和target顺序如何，都属于同一条链路。用Set实现去重是非常合适的方案，核心是给每条链路生成一个和方向无关的唯一标识，用Set记录已经出现过的标识，遍历原数组时只保留第一次出现的链路即可。

具体实现代码 #

const data = [
  { source: "actor0", target: "actor1", value: 2 },
  { source: "actor0", target: "actor2", value: 1 },
  { source: "actor0", target: "actor3", value: 2 },
  { source: "actor0", target: "actor4", value: 3 },
  { source: "actor1", target: "actor0", value: 1 },
  { source: "actor1", target: "actor2", value: 1 },
  { source: "actor1", target: "actor3", value: 3 },
  { source: "actor1", target: "actor4", value: 1 },
  { source: "actor2", target: "actor0", value: 3 },
  { source: "actor2", target: "actor1", value: 1 },
  { source: "actor3", target: "actor0", value: 1 },
  { source: "actor3", target: "actor1", value: 2 },
  { source: "actor3", target: "actor2", value: 1 },
  { source: "actor4", target: "actor0", value: 2 },
  { source: "actor4", target: "actor2", value: 1 },
  { source: "actor4", target: "actor3", value: 2 }
];

const seenEdges = new Set();
const filteredData = data.filter(link => {
  // 对链路两端节点排序后拼接，生成和方向无关的唯一键，用|分隔避免节点名拼接冲突
  const edgeKey = [link.source, link.target].sort().join('|');
  if (seenEdges.has(edgeKey)) return false;
  seenEdges.add(edgeKey);
  return true;
});

实现说明 #

• 生成唯一键时对节点名做字典序排序，保证actor0->actor1和actor1->actor0生成的key都是actor0|actor1，从根源上消除方向带来的key差异
• 拼接key时使用|这类不会出现在节点命名里的特殊分隔符，避免出现节点名组合歧义（比如节点a+bc和ab+c直接无分隔拼接会得到相同字符串）
• 整个去重逻辑完全不读取value字段，符合判定规则，重复链路会保留遍历顺序中最先出现的那条，最终输出结果和期望结果完全一致

运行代码得到的输出如下：

[
  { source: "actor0", target: "actor1", value: 2 },
  { source: "actor0", target: "actor2", value: 1 },
  { source: "actor0", target: "actor3", value: 2 },
  { source: "actor0", target: "actor4", value: 3 },
  { source: "actor1", target: "actor2", value: 1 },
  { source: "actor1", target: "actor3", value: 3 },
  { source: "actor1", target: "actor4", value: 1 },
  { source: "actor3", target: "actor2", value: 1 },
  { source: "actor4", target: "actor2", value: 1 },
  { source: "actor4", target: "actor3", value: 2 }
]

内容的提问来源于stack exchange，提问作者marielle