Wdrożenie rzadkiego wykresu i wydajność w C++

Question

Obecnie pracuję nad ukierunkowaną strukturą danych wykresu w C++ (brak wzorca GL dla tego projektu). Podstawowa aplikacja będzie identyfikować połączone komponenty i pochłaniacze. Oczekuje się, że wykresy będą rzadkie (górny limit E ~ 4V na krawędziach num) i wszystkie będą miały jednolitą masę. Próbuję zdecydować między listą sąsiedztwa, listą przypadków lub ewentualnie inną reprezentacją, o której jeszcze nie słyszałem (np. Macierz nie jest opcją bc sparsity). Wąskim gardłem będzie prawdopodobnie całkowita przestrzeń i szybkość inicjalizacji wykresu: wykresy będą inicjowane z potencjalnie ogromnych tablic tak, że każdy element w tablicy będzie końcem będącym wierzchołkiem o skierowanej krawędzi do jednego z sąsiednich elementów. Aby uzyskać krawędzie dla każdego wierzchołka, wszystkie sąsiednie elementy muszą zostać najpierw porównane.

Moje pytania są następujące: (1) Która reprezentacja jest zazwyczaj szybsza do zainicjowania, a także szybka do przechodzenia przez system plików BFS, (2) Jakie algorytmy (inne niż wanadowe BFS) umożliwiają znalezienie podłączonych komponentów? Wiem, że to O (V + E) używając BFS (co jest optymalne, jak sądzę), ale martwię się wielkością kolejki pośredniej, ponieważ szerokość wykresu rośnie wykładniczo wraz z wysokością.

Nie mam zbyt dużego doświadczenia w implementacji wykresów, więc byłbym wdzięczny za wszelkie sugestie.

Answer 1

Rozważmy układ następująco:

lista sąsiedztwa mogą być realizowane jako tablica [NX4] (gdzie n oznacza 3, w tym przypadku, i 4, bo mówią, że 4 jest maksymalna liczba krawędzi w danym przypadku) w następującej formie:

2 3 0 0 
3 0 0 0 
0 0 0 0 

wyżej przedstawienie zakłada, że ​​liczba wierzchołków posortowanych w porządku, w którym pierwszy indeks w tablicy określał (v-1).

Z drugiej strony lista zdarzeń wymaga zdefiniowania listy wierzchołków, listy krawędzi i elementów połączenia pomiędzy (incidence list - graph).

Obie są dobre pod względem wykorzystania przestrzeni w porównaniu do macierzy sąsiedztwa, ponieważ wykres jest bardzo nieliczny, jak stwierdzono.

Moja sugestia dotyczyłaby listy przyległości, którą można zainicjować jako [Nx4] ciągłą tablicę w pamięci (ponieważ mówisz, że będziesz mieć maksymalnie 4 krawędzie dla jednego wierzchołka). Ta reprezentacja będzie szybsza do zainicjowania. (Ponadto, ta reprezentacja będzie działać lepiej pod względem wydajności pamięci podręcznej:)

Jeśli jednak liczysz na dynamiczny i zmieniający się rozmiar wykresu, listy występowania mogą być lepsze, ponieważ są generalnie zaimplementowane jako listy, które są nie sąsiadujące spacje (patrz link powyżej). De-alokacja i przydział tablicy sąsiedniej mogą być w tym przypadku niepożądane.

Answer 2

Najbardziej efektywnym sposobem implementacji wykresu dla swoich celów jest prawdopodobnie połączenie listy przyległości dla każdego wierzchołka i dodatkowo struktura mieszająca, która mapuje pary wierzchołków na krawędzie, jeśli istnieją. Będzie to wymagało przestrzeni O (| V | + | E |) dla listy sąsiednich O (| E |) dla struktury mieszania i daje oczekiwane O (1) containsEdge(vertex v, vertex w), insertEdge(vertex v, vertex w) i removeEdge(vertex v, vertex w) za pomocą mapowania, aby uzyskać wskaźniki wymagane do szybkiego modyfikowania list sąsiednich wierzchołków.