Wie finde ich in der linearen Zeit einen Superstar?

Question

Betrachten Sie gerichtete Grafiken. Wir nennen einen Knoten $ v $ Superstar Wenn und nur wenn kein anderer Knoten daraus erreicht werden kann, aber alle anderen Knoten haben einen Vorsprung von $ v $. Formal:

$ qquad displayStyle $ v $ text {Superstar}: longleftrightarrow mathrm {out

mit $ n $ die Anzahl der Knoten im Diagramm. In der folgenden Grafik ist der ungefüllte Knoten beispielsweise ein Superstar (und die anderen Knoten nicht).

^[Quelle]

Wie können Sie alle Superstars in einer gerichteten Grafiken in $ mathcal {o} (n) $ identifizieren? Eine geeignete Diagrammdarstellung kann aus dem ausgewählt werden übliche Kandidaten; Bitte unterlassen Sie die Verwendung von Darstellungen, die die Komplexität des Problems in die Vorverarbeitung verschieben.

Es können keine Annahmen in Bezug auf Dichte getroffen werden. Wir gehen nicht davon aus, dass die Grafik einen Superstar enthält. Wenn es keine gibt, sollte der Algorithmus ihn erkennen.

Notation: $ mathrm {outdeg} $ ist die Anzahl der ausgehenden Kanten eines Knotens, $ mathhrm {Indeg} $ ähnlich für eingehende Kanten.

Answer 1

Wir können alle bis auf einen der Scheitelpunkte beseitigen, indem wir nach der Existenz von $ N-1 $ -Kanten überprüfen, da wir eine Möglichkeit für jede Kante beseitigen können, die wir überprüfen. Insbesondere, wenn ein Vorteil von $ $ $ $ $ y $ liegt, eliminieren wir $ x $ und überziehen bis $ y $ (da ein weiterer Scheitelpunkt davon erreicht werden kann); Wenn nicht, eliminieren wir $ y $ (da es nicht von $ x $ erreicht werden kann). Sobald wir den letzten Scheitelpunkt erreicht haben, sollte der Scheitelpunkt, den nicht beseitigt wird, miteinander verglichen werden (stellen Sie sicher, dass die Superstar -Bedingung bestätigt wird: Es gibt ein ankommendes Kanten, das jedoch nicht kontaktfreudig ist), bis er als Superstar beseitigt oder bestätigt wird. Einige Pseudocode:

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

Gehen wir durch ein Beispiel, um die Methode zu veranschaulichen. Nehmen Sie dieses Array mit dem Quellscheitelpunkt oben und dem Ziel an der Seite. 1 zeigt eine Kante an:

$$ begin{array}{r|cccc|r} & 1 & 2 & 3 & 4 hline 1 & - & 1 & 0 & 1 2 & 1 & - & 0 & 1 3 & 1 & 1 & - & 1 4 & 1 & 1 & 0 & - End {Array} $$

Ich werde die Eckpunkte, die wir als potenzielle Superstars ausgeschlossen haben, ausgrauen. Ich werde Green und Rot verwenden, um die Kanten anzugeben, die wir uns ansehen, wenn sie es tun, und nicht die Kante enthalten, nach der wir suchen, und blau, um anzuzeigen, wo wir bereits geschaut haben.

Wir beginnen uns zunächst die Eckpunkte 1 und 2.

$$ begin {array} {r | cccc} & 1 & 2 & 3 & 4 hline 1 & - & color {green} {1} & 0 & 1 2 & 1 & - & 0 & - & 0 & 1 3 & 1 & 1 & - & 1 4 & 1 & 1 & 0 & - End {Array} $$ Die grüne Nummer zeigt, dass es eine Kante von 2 bis 1 gibt, also eliminieren wir 2 und eliminieren wir 2 und eliminieren wir. Suchen Sie nach einer Kante von 3 bis 1:

$$ begin {array} {r | cccc} & 1 & color {grau} {2} & 3 & 4 hline 1 & - & color {blau} {1} & color {rot} { 0} & 1 color {grau} {2} & 1 & - & 0 & 1 3 & 1 & 1 & - & 1 4 & 1 & 1 & 0 & - End {Array } $$

Wir sehen, dass es keine solche Kante gibt, also eliminieren wir 1 und nehmen 3 als unseren aktuellen Scheitelpunkt. Denken Sie daran, dass wir bereits 2 beseitigt haben. Sehen Sie also, ob es eine Kante von 4 bis 3 gibt:

$$ begin {array} {r | cccc} & color {grau} {1} & color {grau} {2} & 3 & 4 hline color {grau} {1} & - & Farbe {blau} {1} & color {blau} {0} & 1 color {grau} {2} & 1 & - & 0 & 1 3 & 1 & 1 & - & Color {grün } {1} 4 & 1 & 1 & 0 & - end {Array} $$

Es gibt eine Kante von 4 bis 3, also eliminieren wir 4. Zu diesem Zeitpunkt haben wir alle bis auf einen der Eckpunkte (3) beseitigt. Schauen Sie sich also die Kanten an und sehen Sie, ob sie sich qualifiziert:

$$ begin {array} {r | cccc} & color {grau} {1} & color {grau} {2} & 3 & color {grau} {4} hline color {grau}} {1} & - & color {blau} {1} & color {red} {0} & 1 color {grau} {2} & 1 & - & 0 & 1 3 & color { grün} {1} & 1 & - & color {blau} {1} color {grau} {4} & 1 & 1 & 0 & - end {Array} $$

Es gibt eine Kante von 1 bis 3, aber nicht umgekehrt, also ist 3 immer noch ein Kandidat.

$$ begin {array} {r | cccc} & color {grau} {1} & color {grau} {2} & 3 & color {grau} {4} hline color {grau}} {1} & - & color {blau} {1} & color {blau} {0} & 1 color {grau} {2} & 1 & - & color {rot} {0} & 1 3 & color {blau} {1} & color {green} {1} & - & color {blau} {1} color {grau} {4} & 1 & 1 & 0 & 0 & - end {Array} $$

Es gibt auch eine Kante von 2 bis 3, aber nicht umgekehrt, also ist 3 immer noch ein Kandidat.

$$ begin {array} {r | cccc} & color {grau} {1} & color {grau} {2} & 3 & color {grau} {4} hline color {grau}} {1} & - & color {blau} {1} & color {blau} {0} & 1 color {grau} {2} & 1 & - & color {blau} {0} & 1 3 & color {blau} {1} & color {blau} {1} & - & color {green} {1} color {grau} {4} & 1 & 1 & color { rot} {0} & - end {Array} $$

Es gibt eine Kante von 4 bis 3, aber nicht 3 bis 4; Damit werden unsere Kanten von 3 von 3 abgeschlossen und wir haben festgestellt, dass es sich tatsächlich um einen Superstar handelt.

Da wir einen Scheitelpunkt als möglicher Superstar bei jedem der ersten $ N-1 $ Edge-Schecks beseitigen, ist der beste Fall, dass der $ n $ TH den endgültigen Scheitelpunkt für eine Komplexität von $ n $ eliminiert. Im schlimmsten Fall (der letzte oder zweitletzte Scheitelpunkt ist ein Superstar oder der endgültige Scheck disqualifiziert ihn), vergleichen wir den Kandidaten mit 2 Times (N-1) $ mehr Scheitelpunkte für eine schlimmste Fallkomplexität von 3n-3 $ ($ O (n) $). Dieser Algorithmus ist also $ theta (n) $.

Answer 2

Ist das nicht das Promi -Problem?

Es wird nur einen Superstar (Berühmtheit) geben, wenn es einen gibt.

Wir verwenden die Adjazenzmatrix -Darstellung, wobei $ a [i, j] = 1 $ Wenn es einen gerichteten Rand von $ i $ bis $ J $ gibt, ansonsten ist es 0 $ $. (Ich vermute, das ist erlaubt).

Wenn Sie $ A [i, j] $ (können in $ mathcal {o} (1) $ time) wir mindestens einen von ihnen als Kandidat für die Berühmtheit beseitigen: Wenn $ a [i, J] = 1 $, dann können Sie $ i $ eliminieren. Wenn $ a [i, j] = 0 $, können wir $ j $ entfernen.

Verwalten Sie eine Liste der aktuellen Kandidaten, wobei sie nacheinander eliminieren. Eine verknüpfte Liste sollte ausreichen.

Am Ende können Sie überprüfen, ob Ihr Kandidat tatsächlich ein Superstar ist.

Dieser Algorithmus ist $ mathcal {o} (n) $.

Answer 3

Diese Antwort befasst sich mit der Version der Frage, in der eine Diagrammdarstellung möglich war, nicht die aktuelle Version der Frage.

• Speichern Sie Ihr Diagramm als Paar der Adjazenzliste und umgekehrte Adjazenzliste, wobei jede Liste zusätzlich die Länge der Liste enthält, daher die Nummer out- bzw. In-Poden.

• Vorverarbeitung: Rechenverkehrs-Adjazenzliste (dh die Liste der Insumges). Kostete $ mathcal {o} (| e |) $.

• Überqueren Sie die Listen und wählen Sie einen beliebigen Knoten aus, bei dem die Anzahl der Überschneidungen $ 0 $ beträgt und die Anzahl der In-Elektroden $ N-1 $ beträgt. Kosten $ mathcal {o} (| n |) $.

Answer 4

Nur als Referenz ist dies Pseudocode einer rekursiven Version dessen, was Kevin veröffentlicht hat.

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