javascript - 删除图中的传递边

Question

我有一个图表

因为我可以从 1 到 2 再到 3(即从 1 到 3 再到 2)，所以从 1 到 3 的边是不必要的。

因此，我想直接去掉1和3之间的边。

我该怎么做？我想我应该做广度优先搜索来决定我可以从 1 到哪里。

所以如果我有我所有的节点和边

nodes = [1, 2, 3]
edges = [
  {source: 1, target: 2},
  {source: 1, target: 3},
  {source: 2, target: 3}
]

我要删除

  {source: 1, target: 3},

因为传递性是不必要的，但是我怎么能确定我是否应该删除

  {source: 1, target: 3},

代替

  {source: 2, target: 3}

?

Answer 1

您正在寻找图的传递归约，this article should help .