Jak znaleźć supergwiazdę w czasie liniowym?

Rozważ skierowane wykresy. Nazywamy węzeł supergwiazdą wtedy i tylko wtedy, gdy nie można do niego dotrzeć z żadnego innego węzła, ale wszystkie inne węzły mają krawędź do . Formalnie:$v$ $v$

$\qquad \displaystyle$ v$\text{ superstar } :\Longleftrightarrow \mathrm{outdeg}(v) = 0 \land \mathrm{indeg}(v) = n-1$

z liczba węzłów na wykresie. Na przykład na poniższym wykresie niewypełniony węzeł jest supergwiazdą (a inne węzły nie są).$n$

^{[ źródło ]}

Jak możesz zidentyfikować wszystkie gwiazdy na kierowanych wykresach w czasie ? Odpowiednią reprezentację grafu można wybrać spośród zwykłych kandydatów ; powstrzymaj się od używania reprezentacji, które przenoszą złożoność problemu na proces wstępnego przetwarzania.$\mathcal{O}(n)$

Nie można przyjąć żadnych założeń dotyczących gęstości. Nie zakładamy, że wykres zawiera gwiazdę; jeśli nie ma, algorytm powinien go rozpoznać.

Notacja : to liczba krawędzi wychodzących w węźle, podobny dla krawędzi przychodzących.$\mathrm{outdeg}$$\mathrm{indeg}$

Możemy wyeliminować wszystkie z wyjątkiem jednego z wierzchołków, sprawdzając obecność krawędzi ponieważ możemy wyeliminować jedną możliwość dla każdej sprawdzanej krawędzi. W szczególności, jeśli krawędź biegnie od do , eliminujemy i przechodzimy do (ponieważ można z niej dotrzeć do innego wierzchołka); jeśli nie, eliminujemy (ponieważ nie można do niego dotrzeć z ). Kiedy dotrzemy do ostatniego wierzchołka, którykolwiek wierzchołek nie zostanie wyeliminowany, należy go porównać ze sobą (upewnij się, że warunek supergwiazdy jest zachowany: istnieje krawędź przychodząca, ale nie wychodząca), dopóki nie zostanie wyeliminowana lub potwierdzona jako supergwiazda. Niektóre pseudokod:$n-1$$x$$y$$x$$y$$y$$x$

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

Przejdźmy przez przykład, aby zilustrować tę metodę. Weź tę tablicę z wierzchołkiem źródłowym u góry i miejscem docelowym z boku. 1 oznacza krawędź:

$$\begin{array}{r|c c c c|r} & 1 & 2 & 3 & 4 \\ \hline 1 & - & 1 & 0 & 1 \\ 2 & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & 1 \\ 4 & 1 & 1 & 0 & - \\ \end{array}$$

Wyszarzę wierzchołki, które wykluczyliśmy jako potencjalne gwiazdy. Użyję zielonego i czerwonego, aby wskazać krawędzie, na które patrzymy, kiedy to robią i nie zawierają krawędzi, której szukamy, i niebieskiej, aby wskazać, gdzie już patrzyliśmy.

Zaczynamy od spojrzenia na wierzchołki 1 i 2.

$$\begin{array}{r|c c c c} & 1 & 2 & 3 & 4 \\ \hline 1 & - & \color{green}{1} & 0 & 1 \\ 2 & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & 1 \\ 4 & 1 & 1 & 0 & - \\ \end{array}$$ Zielona liczba pokazuje, że krawędź jest od 2 do 1, więc eliminujemy 2 i szukamy krawędzi od 3 do 1:

$$\begin{array}{r|c c c c} & 1 & \color{grey}{2} & 3 & 4 \\ \hline 1 & - & \color{blue}{1} & \color{red}{0} & 1 \\ \color{grey}{2} & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & 1 \\ 4 & 1 & 1 & 0 & - \\ \end{array}$$

Widzimy, że nie ma takiej krawędzi, więc eliminujemy 1 i bierzemy 3 jako nasz aktualny wierzchołek. Przypomnijmy, że już wyeliminowaliśmy 2, więc sprawdź, czy jest krawędź od 4 do 3:

$$\begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & 4 \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{blue}{0} & 1 \\ \color{grey}{2} & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & \color{green}{1} \\ 4 & 1 & 1 & 0 & - \\ \end{array}$$

Istnieje krawędź od 4 do 3, więc eliminujemy 4. W tym momencie wyeliminowaliśmy wszystkie z wyjątkiem jednego z wierzchołków (3), więc sprawdź jego krawędzie i sprawdź, czy się kwalifikuje:

$$\begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{red}{0} & 1 \\ \color{grey}{2} & 1 & - & 0 & 1 \\ 3 & \color{green}{1} & 1 & - & \color{blue}{1} \\ \color{grey}{4} & 1 & 1 & 0 & - \\ \end{array}$$

Istnieje przewaga od 1 do 3, ale nie odwrotnie, więc 3 nadal jest kandydatem.

$$\begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{blue}{0} & 1 \\ \color{grey}{2} & 1 & - & \color{red}{0} & 1 \\ 3 & \color{blue}{1} & \color{green}{1} & - & \color{blue}{1} \\ \color{grey}{4} & 1 & 1 & 0 & - \\ \end{array}$$

Istnieje również przewaga od 2 do 3, ale nie odwrotnie, więc 3 wciąż jest kandydatem.

$$\begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{blue}{0} & 1 \\ \color{grey}{2} & 1 & - & \color{blue}{0} & 1 \\ 3 & \color{blue}{1} & \color{blue}{1} & - & \color{green}{1} \\ \color{grey}{4} & 1 & 1 & \color{red}{0} & - \\ \end{array}$$

Istnieje krawędź od 4 do 3, ale nie od 3 do 4; która kończy naszą kontrolę krawędzi 3 i odkryliśmy, że jest to supergwiazda.

Ponieważ eliminujemy jeden wierzchołek jako możliwą supergwiazdę na każdej z pierwszych kontroli krawędzi , najlepszym przypadkiem jest to, że ta kontrola eliminuje końcowy wierzchołek dla złożoności . W najgorszym przypadku (ostatni lub przedostatni wierzchołek jest supergwiazdą lub ostateczna kontrola go dyskwalifikuje), po pierwszych porównaniach porównujemy kandydata z więcej wierzchołków, dla najgorszy przypadek złożoności ( ). Ten algorytm to .$n-1$$n$$n$$n-1$$2\times(n-1)$$3n-3$$O(n)$$\Theta(n)$

Czy to nie problem z celebrytą ?

Będzie tylko jedna supergwiazda (gwiazda), jeśli taka istnieje.

Używamy reprezentacji macierzy przyległości, gdzie jeśli istnieje skierowana krawędź od do , w przeciwnym razie jest to . (Zgaduję, że jest to dozwolone).i j $A[i,j] = 1$$i$$j$$0$

Patrząc na (można to zrobić za czas), możemy wyeliminować co najmniej jednego z nich jako kandydata na celebrytę: Jeśli , następnie można wyeliminować . Jeśli , możemy wyeliminować .O ( 1 ) A [ i , j ] = 1 i A [ i , j ] = 0 $A[i,j]$$\mathcal{O}(1)$$A[i,j] = 1$$i$$A[i,j] = 0$$j$

Utrzymuj listę aktualnych kandydatów, eliminując jeden po drugim. Połączona lista powinna wystarczyć.

Na koniec możesz sprawdzić, czy twój kandydat jest rzeczywiście gwiazdą.

Algorytmem będzie .$\mathcal{O}(n)$

Ta odpowiedź dotyczy wersji pytania, w której możliwa była dowolna reprezentacja graficzna, a nie bieżącej wersji pytania.

• Przechowuj wykres jako parę listy sąsiedztwa i odwróconej listy sąsiedztwa, gdzie każda lista zawiera dodatkowo długość listy, a zatem odpowiednio liczbę na zewnątrz i na krawędzi.

• Przetwarzanie wstępne: oblicz listę odwrotnego przylegania (to znaczy listę krawędzi wewnętrznych). Koszt .$\mathcal{O}(|E|)$

• Przejdź przez listy i wybierz dowolny węzeł, w którym liczba krawędzi zewnętrznych wynosi a liczba krawędzi wewnętrznych wynosi . Koszt .n - 1 O ( | N |$0$$n-1$$\mathcal{O}(|N|)$

Dla odniesienia jest to pseudokod rekurencyjnej wersji tego, co opublikował Kevin.

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