Bellekte bir grafik saklamak için üç yolu vardır:

1. İşaretçiler, nesneleri ve kenarları gibi düğümler
2. Bir matris numaralı düğüm arasındaki kenar ağırlıkları x ve y içeren düğüm
3. Numaralandırılmış düğümler arasındaki kenarlar listesi

Her üç yazmak için nasıl biliyorum, ama her avantajları ve dezavantajları tüm düşündüm emin değilim.

Bellekte bir grafik depolama bu yollardan her birinin avantaj ve dezavantajları nelerdir?

Bu analiz için bir yolu, bellek ve zaman karmaşıklığı grafik erişmek istediğiniz nasıl bağlıdır) açısından.

Bir başka işaretçisi ile nesneler olarak saklanması düğümler

• Bu yaklaşım, bellek karmaşıklığı düğüm gibi çok sayıda nesne var çünkü O(n) ' dir. İşaretçiler (düğüm) sayısı gerekli her düğüm nesne n düğümler için işaretçileri içerebilir olarak O(n^2).
• Bu veri yapısı için zaman karmaşıklığı(n) herhangi bir düğüm erişmek için O.

Kenar ağırlıkları matris depolama

• Bu matris için O(n^2) bellek karmaşıklığı olacaktır.
• Bu veri yapısı ile avantajı herhangi bir düğüm erişmek için zaman karmaşıklığı O(1) ' dir.

Kaç tane grafik üzerinde çalıştırmak ve ne bağlı olarak, uygun bir temsili seçim yapmak zorunda kalacaksın.