Jaki jest najbardziej oszczędny sposób na wdrożenie struktury danych wykresu?

14

Zazwyczaj implementuję wykresy jako podwójnie połączone listy, ale z mojego doświadczenia jest to dość nieefektywne, ponieważ potrzebuję k wskaźników / referencji dla k sąsiadów, więc dla niekierowanego wykresu miałbym ~ 2k sąsiednich linków na listach, jeśli moja matematyka ma rację. Czy istnieje lepszy sposób na zaoszczędzenie miejsca? Wiem, że niektóre linki mogą być osobliwe, jeśli wykres jest skierowany, ale czy istnieje sposób, aby zrobić to lepiej?

data-structures

— Inżynier świata
źródło

12

Cóż, jeśli zależy Ci na wydajności przestrzeni, najlepiej skompresowana struktura danych byłaby najlepsza - ale oczywiście nie jest to zbyt wydajne w przypadku dostępu lub aktualizacji .....

Jeśli wykres ma stosunkowo niewielką liczbę węzłów i jest dość gęsty (powiedzmy, że istnieje co najmniej 5% wszystkich możliwych połączeń), może okazać się, że utworzenie macierzy przylegania jest bardziej efektywne pod względem miejsca niż używanie list krawędzi. Wymagałoby to tylko jednego bitu na możliwe (ukierunkowane) połączenie, a łącznie n * n bitów tam, gdzie masz n węzłów.

W przeciwnym razie, jeśli chcesz użyć łączy sąsiednich, nie możesz zrobić lepiej niż jeden odnośnik na link, ponieważ jest to minimalna zawartość informacyjna, którą musisz przechowywać. Jeśli chcesz mieć linki zwrotne, będziesz potrzebował dwa razy więcej linków.

Istnieje kilka sztuczek, które możesz wypróbować. Na przykład możesz spróbować udostępnić podzbiory linków (jeśli A i B odnoszą się do każdego z C, D, E, to zapisz listę łączy C, D, E tylko raz .....). Jednak stanie się to dość szybko złożone i wątpię, że w większości przypadków będzie to warte wysiłku.

Jeszcze jedna sztuczka - zakładając, że Twój wykres ma rozsądną liczbę węzłów, z pewnością zaoszczędzisz miejsce przez indeksowanie - np. Używając 16-bitowego numeru indeksu węzła zamiast pełnego wskaźnika / odwołania.

— mikera
źródło

Jeśli wszystkie łącza nie są skierowane, można zaoszczędzić połowę miejsca, zapisując tylko krawędź od niskiego węzła do wysokiego węzła.

— Deduplicator

6

Będzie to zależeć od struktury danych.

W przypadku gęstego wykresu z nieukierunkowanymi krawędziami nie można tak naprawdę pokonać listy zestawów bitów reprezentujących trójkątną matrycę. A List<BitArray>na przykład. Logicznie wyglądałoby to tak:

Stamtąd możesz użyć indeksu głównego BitArray, aby zindeksować listę, która przechowuje dane twojego węzła.

Na przykład uzyskanie wszystkich sąsiadów węzła wyglądałoby następująco:

// C#
List<Node> Nodes = /* populated elsewhere */
List<BitArray> bits = /* populated elsewhere */
public static IEnumerable<Node> GetNeighbours(int x)    
{
    for (int i = 0; i < bits[idx].Count; i++)
    {
        if (this.bits[idx][i])
            yield return this.Nodes[i];
    }

    for (int i = 0; i < this.Nodes.Count; i++)
    {
        if (idx < this.bits[i].Count && this.bits[i][idx])
            yield return this.Nodes[i];
    }    
}

(zwróć uwagę, że możesz także wybrać typ indeksu, w zależności od ilości danych, aby był to bajt, ushort lub coś podobnego, ponieważ wszystkie indeksy będą dodatnie. Nie uważam tego za mikrooptymalizację, ponieważ jest to trywialne)

W przypadku grafu ukierunkowanego wybrałbyś trasę * n tablicy bitów do przechowywania łączności ... chyba że jest ona bardzo rzadka w porównaniu do liczby węzłów, gdzie możesz przejść do listy sąsiadujących indeksów.

— Steven Evers
źródło