过滤与候选人有联系的图节点

Question

我想要 filter 一个列表，这样我就只会得到有连接的节点，直接或间接有候选人

  var candidate = 1;
  var data = [
    { source: 1, target: 2 }, // is connected with 1
    { source: 2, target: 3 }, // is connected with 1
    { source: 6, target: 9 }, // no connection
    { source: 12, target: 15 }, // no connection
    { source: 3, target: 2 }, // is connected with 1
    { source: 5, target: 3 }, // is connected with 1
  ]

我在寻找什么样的算法？

感兴趣的语言是 JavaScript - AFAIK 一些语言会以不同于其他语言的方式实现算法

Answer 1

广度优先搜索：

维护一个 "Maybe" 边的列表（用给定的列表初始化），一个 "Connected" 边的列表（初始化为空）和一个节点列表（初始化为仅包含 "candidate").

从节点列表中删除一个节点。
遍历 Maybe 列表，寻找那个节点；如果边包含该节点，则将另一个节点复制到节点列表中并将该边移动到已连接列表中。
继续，直到节点列表为空。

过滤与候选人有联系的图节点

Filter graph nodes that have a connection with a candidate

javascript

graph-theory