过滤图中的节点
问题描述:
我想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一些语言将实现比其他人不同的方式的算法
答
广度优先搜索:
维持的“也许”边缘的名单(给出的初始化列表),“连接”边缘列表(初始化为空)和节点列表(初始化为仅包含“候选者”)。
从节点列表中删除节点。
遍历Maybe列表,查找该节点;如果边缘包含该节点,则将其他节点复制到节点列表中并将该边缘移动到已连接列表中。
继续,直到节点列表为空。
'从节点列表中删除一个节点。'你的意思是可能的列表?节点列表最初只包含候选人 –
@NicholasKyriakides:不,我的意思是节点列表。它最初只包含候选人;删除那个并遍历Maybe列表,寻找该节点。如果在最后,节点列表是空的,那么你就完成了:没有边连接到候选者。 – Beta