2つのノードが同じツリー/グラフの一部であるかどうかを調べる方法は？

Question

インタビューでこの質問をして、2人が直接的または間接的にFacebookに接続しているかどうかを判断しました。

aには友人b、c、d、e、cがあり、友達b、d、f、g、fには友人x、y、zがいます。 aとzは間接的な友人です。

どのように接続されているかを知る良いアルゴリズムはありますか？

This投稿には同じような質問がありましたが、彼はあまりにも多くの基準を持っていましたので、もっと良い方法があるはずだと思いました。誰でもちょっとアドバイスできますか？

Answer 1

Breadth First Searchを実行して、到達可能な場合はその特定の友人に到達する最小のホップを取得します。今まで訪問したノードを保つ一部の書籍では、友人を横断して検索されている友人に届くようになります。

このアルゴリズムは、ライナー時間O(V + E)で実行されます。

擬似コード：

幅優先-検索（グラフ、ルート、目標）：

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より大きい場合は、間接的に接続されていると言えます。

これは、接続されているかどうかを確認するためにも使用できます。