Wie kann man feststellen, ob zwei Knoten Teil eines selben Baumes/Graphen sind?

Question

Ich wurde diese Frage in einem Interview gefragt, ob zwei Personen direkt oder indirekt auf Facebook verbunden sind.

sagen, ein einige Freunde B, C, D, E und C hatten einige Freunde b, d, f, g und f hat Freunde x, y, z. dann sind a und z indirekte Freunde.

Gibt es einen guten Algorithmus heraus gefunden, wie sie verbunden sind?

This Post hatte ähnliche Frage, aber er hat zu viele Kriterien, so dass ich dachte, es muss ein besserer Weg, es zu tun. Kann jemand nur Ratschläge geben?

Answer 1

Führen Sie ein Breadth First Search das Minimum zu bekommen hüpft, dass bestimmten Freund, wenn erreichbar zu erreichen. Mit etwas Buchführung auf den bisher besuchten Knoten werden Sie in der Lage sein, die durchquerten Freunde zu erreichen, um den gesuchten Freund zu erreichen.

Dieser Algorithmus läuft in Liner Zeit O(V + E).

psuedocode:

Breite-First-Search (Graph, Wurzel, Tor):

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) 
     } 
    } 
} 

Wenn die Freunde, die vor der Suche nach dem Freund besucht braucht werden gesucht größer als 1 können Sie sagen, dass sie indirekt verbunden sind.

Dies kann auch zu überprüfen, ob sie verbunden sind oder nicht verwendet werden.