Algorithmus zur Berechnung des Quadrats eines gerichteten Graphen (dargestellt in Form einer Adjazenzliste)

Question

Ich arbeite an der Konstruktion eines Algorithmus zur Berechnung von G^2 eines gerichteten Graphen, der eine Form einer Adjazenzliste ist, wobei G^2 = (V, E '), wobei E' als (u, v) ∈ E definiert ist, wenn es in G einen Pfad der Länge 2 zwischen u und v gibt. Ich verstehe die Frage sehr gut und habe einen Algorithmus gefunden, den ich annehme ist korrekt, jedoch ist die Laufzeit meines Algorithmus O (VE^2), wobei V die Anzahl der Eckpunkte und E die Anzahl der Kanten des Graphen ist. Ich habe mich gefragt, wie ich das in O (VE) Zeit machen könnte, um es effizienter zu machen?

Hier ist der Algorithmus, ich kam mit:

für Vertex in Vertices
für Nachbarn in Nachbarn
für n in Nachbarn
if (! N = Nachbar)
dann-> if (n.value == neighbor)
fügen Sie dies einer neuen Adjazenzliste hinzu
break; // Das bedeutet, dass wir auch weiterhin einen Pfad der Größe 2 zwischen Vertex und Nachbarn
sonst gefunden haben

Answer 1

Das Problem kann O (VE) mit BFS in der Zeit gelöst wird (Breitensuche). Die Sache über BFS ist, dass es das Diagramm level by level durchquert. Das heißt, dass es zuerst alle Scheitelpunkte bei distance of 1 von source vertex durchquert. Dann durchquert es alle Ecken bei distance of 2 von source vertex und so weiter. Also können wir diese Tatsache ausnutzen und unsere BFS beenden, wenn wir Scheitelpunkte bei distance of 2 erreicht haben.

Es folgt der Pseudocode:

For each vertex v in V 
{ 
Do a BFS with v as source vertex 
{ 
    For all vertices u at distance of 2 from v 
    add u to adjacency list of v 
    and terminate BFS 
} 
} 

Da BFS Zeit in Anspruch nimmt O (V + E) und rufen wir dies für jeden Scheitelpunkt, so Gesamtzeit O (V (V + E)) ist, = O (V^2 + VE) = O (VE). Denken Sie nur daran, mit neuen Datenstrukturen für jede BFS Traversierung zu beginnen.