Algoritme komponen yang terhubung dengan kuat untuk grafik berarah

8

Saya telah membaca tentang algoritma untuk menemukan komponen yang sangat terhubung dalam grafik yang diarahkan G=(V,E). Ini mempertimbangkan dua DFS mencari dan langkah kedua adalah transposing grafik asli .GT

Algoritma adalah sebagai berikut:

  1. Jalankan DFS pada (mulai dari titik awal yang berubah-ubah), catat waktu penyelesaian dari semua simpul.G
  2. Hitung transposnya,
  3. Jalankan DFS pada , mulai dari titik dengan waktu penyelesaian terakhir, membentuk pohon yang berakar pada titik tersebut. Setelah pohon selesai, lanjutkan ke vertex yang belum dikunjungi dengan waktu penyelesaian terbaru berikutnya dan bentuk pohon lain menggunakan DFS dan ulangi sampai semua simpul dalam dikunjungi.GTGT
  4. Keluarkan simpul di setiap pohon yang dibentuk oleh DFS kedua sebagai komponen yang terhubung sangat kuat.

Pertanyaanku adalah :

  1. Apa intuisi di balik langkah tengah ini menghitung transpos?
Kutu buku
sumber

Jawaban:

10

Transposing matriks adjecency SEBUAH tidak

SEBUAH[saya,j]=1SEBUAHT[j,saya]=1.

Dalam hal grafik, itu artinya

kamuGvvGTkamu.

Dengan kata lain, transposing membalikkan arah semua tepi. Catat ituGT memiliki komponen kuat yang sama dengan G.

Algoritma yang Anda lihat adalah algoritma Kosaraju . Berhati-hatilah dengan gagasan Anda tentang "waktu penyelesaian": ini bukan waktu simpul dikunjungi, tetapi ketika pencarian telah melintasi subgraf yang dapat dijangkau darinya. Wikipedia mengusulkan untuk menggunakan tumpukan untuk mengelola ini, yang menurut saya adalah ide yang bagus.

Mengapa itu benar untuk digunakan GT, secara intuitif? Menganggapx adalah simpul pertama dari komponen kuatnya yang dikunjungi oleh DFS.

  • DFS menyala G melintasi seluruh komponen kuat dari x setelah mencapai x, ditambah beberapa lainnya melalui tepi yang meninggalkan komponen.
  • Karena kami menggunakan urutan tumpukan untuk mengingat urutan node, x juga merupakan simpul pertama dari komponen kuatnya yang dikunjungi (sebagai simpul awal, datar) pada fase kedua.
  • Sejak G dan GT memiliki komponen kuat yang sama, semua node dalam komponen kuat x dikunjungi saat mencari GT dari x. Tepi tersebut meninggalkan komponen pada titik fase pertama ke arah yang salahGTdan karenanya tidak diikuti. Semua tepi meninggalkan komponenx di GT telah dihapus karena urutan tumpukan.
Raphael
sumber
2

Pemahaman saya:

Saat Anda menjalankan DFS pada grafik DAG apa pun yang melacak waktu penyelesaian, satu - satunya hal yang dapat Anda jamin adalah bahwa simpul wastafel tidak akan pernah mendapatkan waktu penyelesaian tertinggi [1] . Tetapi pada saat yang sama, waktu penyelesaian terendah dapat muncul di komponen grafik mana pun . Oleh karena itu, itu membuat waktu penyelesaian terendah menjadi tidak berguna.

Pada dasarnya, fakta [1] tidak berguna dalam grafik asli juga, tetapi sangat berguna dalam grafik yang ditransformasikan . Saat Anda pindah, pernyataan ini mengarah ke yang berikut:

Dalam grafik transposisi, node yang tenggelam dalam grafik non-transposisi akan selalu mendapatkan waktu penyelesaian tertinggi .

hyahor
sumber