필터 그래프 노드는

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 
    ] 

와 직접 또는 간접

내가 원하는 알고리즘은 무엇입니까?

관심의 언어는 자바 스크립트입니다 - AFAIK 일부 ​​언어는 다른 사람보다 다른 방법으로 알고리즘을 구현하는 것이

Answer 1

폭 우선 검색 :

지정된로 초기화 "어쩌면"가장자리의 목록 (유지 목록), "연결된"가장자리 목록 (초기화 됨) 및 노드 목록 ("후보자"만 포함하도록 초기화 됨)이 포함됩니다.

노드 목록에서 노드를 제거하십시오.
Maybe 목록을 반복하여 해당 노드를 찾습니다. 가장자리에 해당 노드가 포함되어 있으면 다른 노드를 노드 목록에 복사하고 해당 가장자리를 연결됨 목록으로 이동하십시오.
노드 목록이 비어있을 때까지 계속하십시오.