두 노드가 같은 트리/그래프의 일부인지 확인하는 방법은 무엇입니까?

Question

두 사람이 직접 또는 간접적으로 페이스 북에 연결되어 있는지 확인하기 위해 인터뷰에서이 질문을 받았습니다.

a는 몇 명의 친구 b, c, d, e 및 c가 친구 b, d, f, g 및 f가 친구 x, y, z를 가지고 있다고 가정합니다. a와 z는 간접적 인 친구입니다.

그들이 어떻게 연결되어 있는지 알 수있는 좋은 알고리즘이 있습니까?

This 게시물에는 비슷한 질문이 있지만 너무 많은 기준이 있으므로 더 좋은 방법이 있어야한다고 생각했습니다. 누구든지 조언을 할 수 있습니까?

Answer 1

도달하면 해당 친구에게 연락하기 위해 최소 홉 수를 얻으려면 Breadth First Search을 실행하십시오. 지금까지 방문한 노드를 유지하는 일부 책으로 친구를 횡단하여 친구에게 다가가 검색 할 수 있습니다.

이 알고리즘은 Liner time O(V + E)에서 실행됩니다.

는

PsuedoCode는 :

폭 우선-검색 (그래프, 루트, 목표) : 친구를 발견하기 전에 방문해야하는 친구가 검색되는 경우

create empty set Checked 
create empty queue Queue  

add Root to Checked 
Queue.enqueue(Root)      

while Queue is not empty { 
    Current = Queue.dequeue() 
    if Current.has(Goal) { 
     return Current 
    } 
    for each Node that is adjacent to Current { 
     if Node is not in Checked { 
      Checked.add(Node) 
      Queue.enqueue(Node) 
     } 
    } 
} 

입니다 1보다 큰 경우 간접적으로 연결된다고 말할 수 있습니다.

연결되어 있는지 여부를 확인할 때도 사용할 수 있습니다.