Bagaimana menemukan seorang superstar dalam waktu linier?

Pertimbangkan grafik terarah. Kami memanggil superstar simpul jika dan hanya jika tidak ada simpul lain yang dapat dijangkau darinya, tetapi semua simpul lainnya memiliki keunggulan terhadap v . Secara formal:$v$ $v$

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

dengan $n$ jumlah node dalam grafik. Misalnya, dalam grafik di bawah ini, node yang tidak terisi adalah superstar (dan node lainnya tidak).

^{[ sumber ]}

Bagaimana Anda bisa mengidentifikasi semua bintang dalam grafik terarah dalam waktu $\mathcal{O}(n)$ ? Representasi grafik yang sesuai dapat dipilih dari kandidat biasa ; tolong jangan menggunakan representasi yang memindahkan kompleksitas masalah ke preproses.

Tidak ada asumsi tentang kepadatan yang dapat dibuat. Kami tidak menganggap grafik berisi superstar; jika tidak ada, algoritma harus mengenalinya.

Notasi : $\mathrm{outdeg}$ adalah jumlah node tepi keluar, $\mathrm{indeg}$ sama untuk tepi yang masuk.

Kita dapat menghilangkan semua kecuali satu dari simpul dengan memeriksa keberadaan edge karena kita dapat menghilangkan satu kemungkinan untuk setiap edge yang kita periksa. Secara khusus, jika ada sisi bergerak dari x ke y , kita menghilangkan x dan beralih ke y (karena titik lain dapat dicapai darinya); jika tidak, kita hilangkan y (karena tidak dapat dicapai dari x ). Setelah kami mencapai simpul terakhir, simpul mana pun yang tidak dihilangkan harus dibandingkan satu sama lain (pastikan kondisi superstar ditegakkan: ada tepi masuk tetapi tidak keluar) sampai dihapus atau dikonfirmasi sebagai superstar. Beberapa pseudocode:$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

Mari kita telusuri contoh untuk menggambarkan metode ini. Ambil array ini, dengan simpul sumber di atas dan tujuan di samping. 1 menunjukkan tepi:

$$\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}$$

Saya akan menghapus simpul yang telah kita singkirkan sebagai superstar potensial. Saya akan menggunakan hijau dan merah untuk menunjukkan tepi yang kita lihat ketika mereka lakukan dan tidak mengandung tepi yang kita cari, dan biru untuk menunjukkan di mana kita sudah melihat.

Kita mulai dengan melihat simpul 1 dan 2.

Angka hijau menunjukkan ada tepi dari 2 ke 1, jadi kami menghilangkan 2 dan mencari tepi dari 3 ke 1 :

$$\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}$$

$$\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}$$

Kami melihat tidak ada tepi seperti itu, jadi kami menghilangkan 1 dan mengambil 3 sebagai simpul kami saat ini. Ingatlah bahwa kami telah menghilangkan 2, jadi lihat apakah ada keunggulan dari 4 hingga 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}$$

Ada tepi dari 4 hingga 3, jadi kami menghilangkan 4. Pada titik ini kami telah menghilangkan semua kecuali satu dari simpul (3), jadi periksa ujungnya dan lihat apakah memenuhi syarat:

$$\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}$$

Ada keunggulan dari 1 ke 3 tapi bukan sebaliknya, jadi 3 masih kandidat.

$$\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}$$

Ada juga keunggulan dari 2 ke 3 tetapi bukan sebaliknya, jadi 3 masih kandidat.

$$\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}$$

Ada keunggulan dari 4 ke 3 tetapi tidak 3 ke 4; yang melengkapi pemeriksaan 3 sisi kami dan kami telah menemukan bahwa itu sebenarnya adalah seorang superstar.

$n-1$$n$$n$$n-1$$2\times(n-1)$$3n-3$$O(n)$$\Theta(n)$

Bukankah ini Masalah Selebriti ?

Hanya akan ada satu superstar (selebriti) jika ada.

$A[i,j] = 1$$i$$j$$0$

$A[i,j]$$\mathcal{O}(1)$$A[i,j] = 1$$i$$A[i,j] = 0$$j$

Menyimpan daftar kandidat saat ini, menghilangkan satu per satu. Daftar tertaut harus cukup.

Pada akhirnya, Anda dapat memverifikasi apakah kandidat Anda memang seorang superstar.

$\mathcal{O}(n)$

Jawaban ini membahas versi pertanyaan di mana representasi grafik dimungkinkan, bukan versi pertanyaan saat ini.

• Simpan grafik Anda sebagai pasangan daftar adjacency dan membalikkan daftar adjacency, di mana masing-masing daftar berisi tambahan panjang daftar, sehingga jumlah masing-masing out-and in-edge.

• $\mathcal{O}(|E|)$

• $0$$n-1$$\mathcal{O}(|N|)$

Hanya untuk referensi, ini adalah pseudocode dari versi rekursif dari apa yang diposting 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