Wie finde ich einen Superstar in linearer Zeit?

28

Betrachten Sie gerichtete Graphen. Wir nennen einen Knoten v Superstar genau dann, wenn kein anderer Knoten von ihm aus erreichbar ist, aber alle anderen Knoten eine Kante zu v . Formal:

v  Superstar : ⟺OutdeG(v)=0ichndeG(v)=n-1

mit n die Anzahl der Knoten in der Grafik. In der folgenden Grafik ist der ungefüllte Knoten beispielsweise ein Superstar (die anderen Knoten hingegen nicht).

Ein Superstar
[ 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.O(n)

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.outdegindeg

Raphael
quelle
1
Dürfen wir wobei k Kanten sind, oder müssen wir nur O ( 1 ) -Kanten auf jedem Scheitelpunkt betrachten? O(n+k)kO(1)
Kevin
@ Kevin Nein, ist eine strenge Anforderung. Zur zweiten Frage: Ich weiß nicht, ob das überhaupt nötig ist, aber mehr können Sie sicher nicht. O(n)
Raphael
Kennst du die Antwort? Kann es in ? O(n)
Dave Clarke
@ DaveClarke: Ja und ja.
Raphael
Sie sollten die Darstellung weiter einschränken; Ein linearer Algorithmus ist für eine Adjazenzliste nicht möglich (nur um zu bestätigen, dass ein Scheitelpunkt ein Superstar ist, müssen Sie möglicherweise die gesamte Liste an jedem Scheitelpunkt durchgehen).
Gilles 'SO- hör auf böse zu sein'

Antworten:

18

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:n1xyxyyx

vertex superstar(graph g)
    current vertex = first
    # Go through each vertex
    for each subsequent vertex in g ("next")
        # If there's an edge from this to the next, we eliminate this one [move to the new one].
        # If not, we just stay here.
        if edge exists from current to next
            candidate = next
        end if
    end for
    # Now we are on the final remaining candidate, check whether it satisfies the requirements.
    # just a rename for clarity
    candidate = current
    for each other vertex in g
        if edge from current to other exists
            return null 
        else if no edge from other to current
            return null
        end if
    end for
    return candidate
end superstar

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:

12341101210131114110

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 :

12341101210131114110

12341101210131114110

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:

12341101210131114110

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:

12341101210131114110

Es gibt eine Kante von 1 bis 3, aber nicht die Umkehrung, so dass 3 immer noch ein Kandidat ist.

12341101210131114110

There is also an edge from 2 to 3 but not the reverse, so 3 is still a candidate.

12341101210131114110

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 first n1 edge checks, the best case is that the nth 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 n1 comparisons we compare the candidate with 2×(n1) more vertices, for a worst case complexity of 3n3 (O(n)). So, this algorithm is Θ(n).

Kevin
quelle
8

Isn't this the Celebrity Problem?

There will only be one superstar(celebrity) if there is one.

We use the adjacency matrix representation, where A[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 at A[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 be O(n).

Aryabhata
quelle
How do you choose suitable (i,j) in constant time?
Raphael
3
@Raphael: Just pick the first two candidates from the linked list. (head and head->next).
Aryabhata
6

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). Cost O(|E|).

  • Traverse the lists and select any node where the number of out-edges is 0 and the number of in-edges is n1. Cost O(|N|).

Dave Clarke
quelle
Ok, I see that allowing any graph representation is too weak. I restricted the question to what I intended.
Raphael
2

Just for reference, this is pseudocode of a recursive version of what Kevin posted.

superstar(V, E) {
  if ( |V| == 1 ) {
    return V.pop
  }

  a = V.pop
  b = V.pop
  if ( (a,b) ∈ E ) {
    no_ss = a
    keep  = b
  }
  else {
    no_ss = b
    keep = a
  }

  s = superstar(V ++ keep)

  return ( s != null && (no_ss, s) ∈ E && !(s, no_ss) ∈ E ) ? s : null
}

hasSuperstar(V, E) = superstar(V, E) != null
Raphael
quelle