Tiga cara untuk menyimpan grafik dalam memori, kelebihan dan kekurangan

Ada tiga cara untuk menyimpan grafik dalam memori:

1. Node sebagai objek dan tepi sebagai penunjuk
2. Matriks yang berisi semua bobot tepi antara simpul x dan simpul y
3. Daftar tepi antara node bernomor

Saya tahu cara menulis ketiganya, tetapi saya tidak yakin saya telah memikirkan semua kelebihan dan kekurangan masing-masing.

Apa keuntungan dan kerugian dari masing-masing cara menyimpan grafik dalam memori ini?

Salah satu cara untuk menganalisisnya adalah dalam hal memori dan kompleksitas waktu (yang bergantung pada bagaimana Anda ingin mengakses grafik).

Menyimpan node sebagai objek dengan penunjuk satu sama lain

• Kompleksitas memori untuk pendekatan ini adalah O (n) karena Anda memiliki objek sebanyak Anda memiliki node. Jumlah pointer (ke node) yang diperlukan hingga O (n ^ 2) karena setiap objek node dapat berisi pointer hingga n node.
• Kompleksitas waktu untuk struktur data ini adalah O (n) untuk mengakses setiap node yang diberikan.

Menyimpan matriks bobot tepi

• Ini akan menjadi kompleksitas memori O (n ^ 2) untuk matriks.
• Keuntungan dengan struktur data ini adalah kompleksitas waktu untuk mengakses node yang diberikan adalah O (1).

Bergantung pada algoritma apa yang Anda jalankan pada grafik dan berapa banyak node yang ada, Anda harus memilih representasi yang sesuai.

Beberapa hal lagi yang perlu dipertimbangkan:

1. Model matriks lebih mudah digunakan untuk grafik dengan tepi berbobot, dengan menyimpan bobot dalam matriks. Model objek / penunjuk perlu menyimpan bobot tepi dalam larik paralel, yang memerlukan sinkronisasi dengan larik penunjuk.

2. Model objek / penunjuk bekerja lebih baik dengan grafik terarah daripada grafik tidak terarah karena penunjuk perlu dipertahankan berpasangan, yang bisa menjadi tidak sinkron.

Metode objek-dan-penunjuk mengalami kesulitan pencarian, seperti yang telah dicatat beberapa orang, tetapi cukup alami untuk melakukan hal-hal seperti membangun pohon pencarian biner, di mana ada banyak struktur tambahan.

Saya pribadi menyukai matriks kedekatan karena mereka membuat semua jenis masalah menjadi jauh lebih mudah, menggunakan alat dari teori grafik aljabar. (Pangkat k dari matriks ketetanggaan memberikan banyaknya lintasan dengan panjang k dari simpul i ke simpul j, misalnya. Tambahkan matriks identitas sebelum mengambil pangkat k untuk mendapatkan jumlah lintasan dengan panjang <= k. Ambil rank n-1 minor dari Laplacian untuk mendapatkan jumlah pohon yang merentang ... Dan seterusnya.)

Tapi semua orang mengatakan matriks kedekatan mahal untuk memori! Mereka hanya setengah kanan: Anda dapat menyiasatinya menggunakan matriks renggang jika grafik Anda memiliki sedikit tepi. Struktur data matriks renggang bekerja persis dengan hanya menyimpan daftar kedekatan, tetapi masih memiliki keseluruhan operasi matriks standar yang lengkap, memberi Anda yang terbaik dari kedua dunia.

Saya pikir contoh pertama Anda agak ambigu - node sebagai objek dan edge sebagai pointer. Anda dapat melacak ini dengan menyimpan hanya sebuah pointer ke beberapa node root, dalam hal ini mengakses node tertentu mungkin tidak efisien (katakanlah Anda menginginkan node 4 - jika objek node tidak disediakan, Anda mungkin harus mencarinya) . Dalam kasus ini, Anda juga akan kehilangan bagian grafik yang tidak dapat dijangkau dari node root. Saya pikir ini adalah kasus yang diasumsikan f64 rainbow ketika dia mengatakan kompleksitas waktu untuk mengakses node yang diberikan adalah O (n).

Jika tidak, Anda juga bisa menyimpan array (atau hashmap) penuh dengan pointer ke setiap node. Hal ini memungkinkan akses O (1) ke node tertentu, tetapi sedikit meningkatkan penggunaan memori. Jika n adalah jumlah node dan e adalah jumlah edge, kompleksitas ruang dari pendekatan ini adalah O (n + e).

Kompleksitas ruang untuk pendekatan matriks akan berada di sepanjang garis O (n ^ 2) (dengan asumsi tepi searah). Jika grafik Anda jarang, Anda akan memiliki banyak sel kosong di matriks Anda. Tetapi jika grafik Anda sepenuhnya terhubung (e = n ^ 2), ini lebih baik dibandingkan dengan pendekatan pertama. Seperti yang dikatakan RG, Anda mungkin juga memiliki lebih sedikit cache yang hilang dengan pendekatan ini jika Anda mengalokasikan matriks sebagai satu bagian memori, yang dapat membuat banyak tepi di sekitar grafik menjadi lebih cepat.

Pendekatan ketiga mungkin yang paling efisien ruang untuk kebanyakan kasus - O (e) - tetapi akan membuat pencarian semua tepi node tertentu menjadi tugas O (e). Saya tidak bisa memikirkan kasus di mana ini akan sangat berguna.

Lihatlah tabel perbandingan di wikipedia. Ini memberikan pemahaman yang cukup baik tentang kapan harus menggunakan setiap representasi grafik.

Ada pilihan lain: node sebagai objek, edge sebagai objek juga, setiap edge berada pada saat yang sama dalam dua daftar yang terhubung ganda: daftar semua edge yang keluar dari node yang sama dan daftar semua edge yang masuk ke node yang sama .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

Overhead memori besar (2 pointer per node dan 6 pointer per edge) tetapi Anda mendapatkannya

• O (1) penyisipan node
• O (1) penyisipan tepi (penunjuk yang diberikan ke node "dari" dan "ke")
• O (1) penghapusan tepi (diberi penunjuk)
• O (deg (n)) penghapusan node (diberi penunjuk)
• O (deg (n)) menemukan tetangga dari sebuah node

Struktur juga dapat mewakili grafik yang agak umum: multigraph berorientasi dengan loop (yaitu Anda dapat memiliki beberapa tepi yang berbeda antara dua node yang sama termasuk beberapa loop berbeda - tepi berpindah dari x ke x).

Penjelasan lebih rinci tentang pendekatan ini tersedia di sini .

Oke, jadi jika edge tidak memiliki bobot, matriksnya bisa menjadi array biner, dan menggunakan operator biner bisa membuat semuanya berjalan sangat, sangat cepat dalam kasus itu.

Jika grafiknya jarang, metode objek / penunjuk tampaknya jauh lebih efisien. Menyimpan objek / penunjuk dalam struktur data secara khusus untuk membujuknya menjadi satu bagian memori mungkin juga merupakan rencana yang baik, atau metode lain untuk membuat mereka tetap bersama.

Daftar kedekatan - hanya daftar node yang terhubung - sejauh ini tampaknya paling efisien dalam memori, tetapi mungkin juga yang paling lambat.

Membalik grafik berarah mudah dilakukan dengan representasi matriks, dan mudah dengan daftar ketetanggaan, tetapi tidak terlalu bagus dengan representasi objek / penunjuk.