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−1xyxyyx
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ź:
12341−11121−11300−04111−
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.
12341−11121−11300−04111−
Zielona liczba pokazuje, że krawędź jest od 2 do 1, więc eliminujemy 2 i szukamy krawędzi od 3 do 1:
12341−11121−11300−04111−
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:
12341−11121−11300−04111−
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:
12341−11121−11300−04111−
Istnieje przewaga od 1 do 3, ale nie odwrotnie, więc 3 nadal jest kandydatem.
12341−11121−11300−04111−
Istnieje również przewaga od 2 do 3, ale nie odwrotnie, więc 3 wciąż jest kandydatem.
12341−11121−11300−04111−
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−1nnn−12×(n−1)3n−3O(n)Θ(n)
