Kapan daftar kedekatan atau matriks pilihan yang lebih baik?

Saya diberitahu bahwa kami akan menggunakan daftar jika grafik jarang dan matriks jika grafik padat . Bagi saya, itu hanya definisi mentah. Saya tidak melihat banyak hal di luarnya. Bisakah Anda mengklarifikasi kapan akan menjadi pilihan alami?

Terima kasih sebelumnya!

graphs data-structures lists adjacency-matrix pengguna21312
sumber

Terkait: stackoverflow.com/a/2218331/5746050 dan stackoverflow.com/a/5419933/5746050

ryan

Itu bukan definisi, terutama karena tidak ada definisi tunggal "jarang" dan "padat". Juga, ada pertimbangan lain, misalnya aspek grafik mana yang Anda akses seberapa sering.

Raphael

@Raphael Bisakah Anda masuk ke detail lebih lanjut tentang pertimbangan lain?

user21312

@ user21312, perbedaan besar adalah iterability vs akses edge. Jika Anda sering perlu mengulangi tepi maka daftar adj mungkin lebih berguna. Jika Anda sering perlu menentukan apakah ada tepi atau mengakses bobotnya (atau info lainnya) maka matriks mungkin lebih baik.

ryan

Untuk tujuan Anda, kami mungkin bisa ceroboh tentang apa definisi 'jarang' dan 'padat'. Hanya memodelkan kompleksitas waktu dari operasi matriks yang ingin Anda gunakan untuk setiap jenis struktur data dan melihat di mana 'break point of density'. Saya pikir tautan kedua oleh @ryan sedang mencoba melakukan hal serupa

Apiwat Chantawibul

Jawaban:

Pertama-tama perhatikan bahwa jarang berarti Anda memiliki sangat sedikit tepi, dan padat berarti banyak tepi, atau grafik hampir lengkap. Dalam grafik lengkap Anda memiliki edge, di mana adalah jumlah node. $n(n-1)/2$ $n$

Sekarang, ketika kita menggunakan representasi matriks kita mengalokasikan matriks untuk menyimpan informasi simpul-konektivitas, misalnya, jika ada tepi antara node dan , jika . Tetapi jika kita menggunakan daftar adjacency maka kita memiliki array node dan masing-masing node menunjuk ke daftar adjacency yang berisi HANYA node-node tetangga . $n\times n$ $M[i][j] = 1$ $i$ $j$ $M[i][j] = 0$

Sekarang jika grafik jarang dan kami menggunakan representasi matriks maka sebagian besar sel matriks tetap tidak digunakan yang mengarah pada pemborosan memori. Jadi kita biasanya tidak menggunakan representasi matriks untuk grafik jarang. Kami lebih suka daftar kedekatan.

Tetapi jika grafiknya padat maka jumlah ujungnya mendekati (lengkap) , atau ke jika grafik diarahkan dengan loop otomatis. Maka tidak ada keuntungan menggunakan daftar adjacency atas matriks. $n(n-1)/2$ $n^2$

Dalam hal kompleksitas ruang,
matriks Adjacency: Daftar Adjacency: mana adalah jumlah node, adalah jumlah tepi. $O(n^2)$
$O(n + m)$
$n$ $m$

Ketika grafik tidak diarahkan pohon maka
Adjacency matrix: Daftar Adjacency: adalah (lebih baik dari ) $O(n^2)$
$O(n + n)$ $O(n)$ $n^2$

Ketika grafik diarahkan, lengkap, dengan loop otomatis maka
Adjacency matrix: Daftar Adjacency: adalah (tidak ada perbedaan) $O(n^2)$
$O(n + n^2)$ $O(n^2)$

Dan akhirnya, ketika Anda menerapkan menggunakan matriks, memeriksa apakah ada tepi antara dua node membutuhkan kali, sementara dengan daftar adjacency, mungkin butuh waktu linier dalam . $O(1)$ $n$

fade2black
sumber

"sementara dengan daftar adjacency, mungkin butuh waktu linier" - Mengingat daftar adjacency Anda (mungkin) tidak memiliki urutan alami, mengapa daftar itu bukan hash set?

Kevin

@Kevin Kemudian akan disebut "adjacency hash", bukan "daftar". Juga mungkin, mengapa tidak? Tetapi jika Anda hanya melakukan DFS atau BFS, atau beberapa prosedur lain yang memindai secara sistematis semua node, lalu apa keuntungan menggunakan hash over list? Bagaimanapun Anda akan memeriksa semua node yang berdekatan.

fade2black

Saya akan menambahkan bahwa dalam kasus tanpa diarahkan unweighted, untuk grafik yang hampir lengkap mungkin lebih layak untuk menyimpan komplemennya, yaitu grafik jarang. Jadi, sebuah matriks berguna ketika kira-kira setengah dari tepiannya ada.

M. Musim Dingin

Untuk menjawab dengan memberikan analogi sederhana .. Jika Anda harus menyimpan 6oz air, apakah Anda (secara umum) melakukannya dengan wadah 5 galon, atau cangkir 8oz?

Sekarang, kembali ke pertanyaan Anda .. Jika mayoritas matriks Anda kosong, lalu mengapa menggunakannya? Cukup daftarkan setiap nilai saja. Namun, jika daftar Anda sangat panjang, mengapa tidak menggunakan matriks untuk menyingkatnya?

Alasan di balik daftar vs matriks sangat sederhana dalam kasus ini.

Daftar PS benar-benar hanya satu matriks kolom !!! (Mencoba menunjukkan kepada Anda betapa sewenang-wenangnya suatu keputusan / skenario ini)

Charles
sumber

Pertimbangkan grafik dengan node dan edge. Mengabaikan istilah orde rendah, matriks bit untuk grafik menggunakan bit tidak peduli berapa banyak tepinya. $N$ $E$ $N^2$

Berapa banyak bit yang sebenarnya Anda butuhkan?

Dengan asumsi bahwa tepi adalah independen, jumlah grafik dengan node dan edge adalah $N$ $E$ . Jumlah minimum bit yang diperlukan untuk menyimpan subset ini adalah ${N^2 \choose E}$ . $\log_2 {N^2 \choose E}$

Kami akan menganggap tanpa kehilangan generalisasi bahwa , yaitu, bahwa setengah atau lebih sedikit dari tepi ada. Jika ini bukan masalahnya, kita dapat menyimpan set "non-edge" sebagai gantinya. $E \le \frac{N^2}{2}$

Jika , $E = \frac{N^2}{2}$ , sehingga representasi matriks optimal asimtotik. Jika, menggunakan perkiraan Stirling dan sedikit aritmatika, kami menemukan: $\log_2{N^2 \choose E} = N^2 + o(N^2)$ $E \ll N^2$

{catatan}_{2} (\binom{N^{2}}{E})

$\log_2 {N^2 \choose E}$

= {catatan}_{2} \frac{(N^{2})!}{E! (N^{2} - E)!}

$= \log_2 \frac {(N^2)!} {E! (N^2 - E)!}$

= 2 E {catatan}_{2} N + HAI (ketentuan pesanan rendah)

$= 2E \log_2 N + O(\hbox{low order terms})$

Jika Anda menganggap bahwa adalah ukuran bilangan bulat yang dapat mewakili indeks simpul, representasi optimal adalah array dari id simpul , yaitu array pasangan indeks simpul. $\log_2 N$ $2E$

Karena itu, ukuran yang baik dari sparsity adalah entropi, yang juga merupakan jumlah bit per tepi dari representasi optimal. Jika adalah probabilitas bahwa ada sebuah edge, entropinya adalah. Untuk $p = \frac{E}{N^2}$ $- \log_2{p(1-p)}$ $p \approx \frac{1}{2}$

Nama samaran
sumber