Betrachten Sie gerichtete Graphen. Wir nennen einen Knoten Superstar genau dann, wenn kein anderer Knoten von ihm aus erreichbar ist, aber alle anderen Knoten eine Kante zu . Formal:
v
mit die Anzahl der Knoten in der Grafik. In der folgenden Grafik ist der ungefüllte Knoten beispielsweise ein Superstar (die anderen Knoten hingegen nicht).
[ Quelle ]
Wie können Sie alle Superstars in einer gerichteten Grafik in Zeit identifizieren ? Eine geeignete Graphendarstellung kann aus den üblichen Kandidaten ausgewählt werden ; Verwenden Sie bitte keine Darstellungen, die die Komplexität des Problems auf die Vorverarbeitung verlagern.
Es können keine Annahmen bezüglich der Dichte gemacht werden. Wir gehen nicht davon aus, dass die Grafik einen Superstar enthält. Wenn es keine gibt, sollte der Algorithmus sie erkennen.
Notation : eines Knotens Anzahl von ausgehenden Kanten ist, i n d e g ähnliche für ankommende Kanten.
quelle
Antworten:
Wir können alle Eckpunkte bis auf einen beseitigen, indem wir prüfen, ob Kanten vorhanden sind, da wir für jede von uns überprüfte Kante eine Möglichkeit beseitigen können. Insbesondere wenn es eine Kante gibt, die von x nach y geht , eliminieren wir x und bewegen uns weiter nach y (da von dort aus ein anderer Scheitelpunkt erreicht werden kann); wenn nicht, eliminieren wir y (da es von x aus nicht erreichbar ist ). Sobald wir den letzten Scheitelpunkt erreicht haben, sollte jeder Scheitelpunkt, der nicht beseitigt ist, miteinander verglichen werden (stellen Sie sicher, dass die Superstar-Bedingung eingehalten wird: Es gibt eine Kante, die ankommt, aber nicht abgeht), bis er beseitigt oder als Superstar bestätigt wird. Ein Pseudocode:n−1 x y x y y x
Lassen Sie uns ein Beispiel durchgehen, um die Methode zu veranschaulichen. Nehmen Sie dieses Array mit dem Quellscheitelpunkt oben und dem Ziel an der Seite. 1 zeigt eine Kante an:
Ich werde die Eckpunkte, die wir als potenzielle Superstars ausgeschlossen haben, grau machen. Ich werde grün und rot verwenden, um die Kanten anzuzeigen, auf die wir schauen, wenn sie die gesuchte Kante enthalten, und blau, um anzuzeigen, wo wir bereits gesucht haben.
Zunächst betrachten wir die Eckpunkte 1 und 2.
Die grüne Zahl zeigt an, dass es eine Kante von 2 bis 1 gibt, also eliminieren wir 2 und suchen nach einer Kante von 3 bis 1 :
Wir sehen, dass es keine solche Kante gibt, also eliminieren wir 1 und nehmen 3 als unseren aktuellen Scheitelpunkt. Denken Sie daran, dass wir 2 bereits eliminiert haben, und prüfen Sie, ob es eine Kante von 4 nach 3 gibt:
Da es eine Kante von 4 bis 3 gibt, eliminieren wir 4. An diesem Punkt haben wir alle Ecken bis auf einen (3) eliminiert. Sehen Sie sich also die Kanten an und prüfen Sie, ob sie qualifiziert sind:
Es gibt eine Kante von 1 bis 3, aber nicht die Umkehrung, so dass 3 immer noch ein Kandidat ist.
There is also an edge from 2 to 3 but not the reverse, so 3 is still a candidate.
There is an edge from 4 to 3 but not 3 to 4; that completes our check of 3's edges and we have found that it is, in fact, a superstar.
Since we eliminate one vertex as a possible superstar on each of the firstn−1 edge checks, the best case is that the n th check eliminates the
final vertex for a complexity of n . In the worst case (the last or
second-to-last vertex is a superstar, or the final check disqualifies it), after the first n−1 comparisons we compare the candidate
with 2×(n−1) more vertices, for a worst case complexity of 3n−3 (O(n) ). So, this algorithm is
Θ(n) .
quelle
Isn't this the Celebrity Problem?
There will only be one superstar(celebrity) if there is one.
We use the adjacency matrix representation, whereA[i,j]=1 if there is a directed edge from i to j , otherwise it is 0 . (I am guessing that is allowed).
By looking atA[i,j] (can be done in O(1) time) we can eliminate at least one of them as a candidate for being the celebrity: If A[i,j]=1 , then you can eliminate i . If A[i,j]=0 we can eliminate j .
Maintain a list of current candidates, eliminating one by one. A linked list should suffice.
At the end, you can verify if your candidate is indeed a superstar.
This algorithm will beO(n) .
quelle
This answer addresses the version of the question where any graph representation was possible, not the current version of the question.
Store your graph as a pair of adjacency list and reverse adjacency list, where each list contains in addition the length of the list, hence the number out- and in-edges, respectively.
Preprocessing: compute reverse adjacency list (that is, the list of in-edges). CostO(|E|) .
Traverse the lists and select any node where the number of out-edges is0 and the number of in-edges is n−1 . Cost O(|N|) .
quelle
Just for reference, this is pseudocode of a recursive version of what Kevin posted.
quelle