Porównanie reprezentacji grafów obiektów z listą sąsiedztwa i reprezentacjami macierzowymi

Obecnie postępuję zgodnie z radą Steve'a Yegge'a dotyczącą przygotowania do wywiadu technicznego z zakresu programowania: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

W swojej sekcji na temat wykresów stwierdza:

Istnieją trzy podstawowe sposoby przedstawiania wykresu w pamięci (obiekty i wskaźniki, macierz i lista przylegania) i należy zapoznać się z każdą reprezentacją oraz jej zaletami i wadami.

Zalety i wady reprezentacji macierzy i list przylegania są opisane w CLRS, ale nie byłem w stanie znaleźć zasobu, który porównałby je z reprezentacją obiektu.

Wystarczy pomyśleć o tym, że sam mogę to wywnioskować, ale chciałbym się upewnić, że nie przegapiłem czegoś ważnego. Gdyby ktoś mógł to kompleksowo opisać lub wskazać mi źródło, które to robi, byłbym bardzo wdzięczny.

obiekty i wskaźniki

To tylko podstawowe struktury danych, jak Hammar powiedział w drugiej odpowiedzi, w Javaktórych przedstawiłbyś to za pomocą klas takich jak krawędzie i wierzchołki. Na przykład krawędź łączy dwa wierzchołki i może być skierowana lub nie skierowana i może zawierać ciężar. Wierzchołek może mieć identyfikator, nazwę itp. Przeważnie oba mają dodatkowe właściwości. Możesz więc zbudować swój wykres z nimi, jak

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30  

Takie podejście jest powszechnie stosowane w implementacjach zorientowanych obiektowo, ponieważ jest bardziej czytelne i wygodne dla użytkowników zorientowanych obiektowo;).

matryca

Macierz to po prostu prosta dwuwymiarowa tablica. Zakładając, że masz identyfikatory wierzchołków, które można przedstawić jako tablicę int w następujący sposób:

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

Jest to często używane w przypadku gęstych wykresów, w których wymagany jest dostęp do indeksu. Za pomocą tego można przedstawić strukturę bez / ukierunkowaną i ważoną.

lista sąsiedztwa

To tylko prosta mieszanka danych, zwykle implementuję ją za pomocą pliku HashMap<Vertex, List<Vertex>>. Podobnie używany może być HashMultimapw guawie.

To podejście jest fajne, ponieważ masz wyszukiwanie wierzchołków O (1) (amortyzowanych) i zwraca mi listę wszystkich sąsiednich wierzchołków do tego konkretnego wierzchołka, którego żądałem.

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

Służy do przedstawiania rzadkich wykresów, jeśli aplikujesz w Google, powinieneś wiedzieć, że wykresy internetowe są rzadkie. Możesz sobie z nimi poradzić w bardziej skalowalny sposób, korzystając z BigTable .

Aha, tak przy okazji, oto bardzo dobre podsumowanie tego postu z fantazyjnymi zdjęciami;)

Obiekty i wskaźniki są w większości takie same jak lista przylegania, przynajmniej w celu porównywania algorytmów używających tych reprezentacji.

Porównać

struct Node {
    Node *neighbours[];
};

z

struct Node {
    Node *left;
    Node *right;
};

W tym drugim przypadku możesz łatwo utworzyć listę sąsiadów w locie, jeśli jest łatwiejsza w pracy niż nazwane wskaźniki.

Zaletą reprezentacji obiektu ( listy zdarzeń ) jest to, że dwa sąsiednie wierzchołki mają to samo wystąpienie krawędzi. Ułatwia to manipulowanie nieukierunkowanymi danymi dotyczącymi krawędzi (długość, koszt, przepływ, a nawet kierunek). Jednak używa dodatkowej pamięci na wskaźniki.

Kolejne dobre źródło: Khan Academy - „Reprezentowanie wykresów”

Oprócz listy sąsiedztwa i macierzy sąsiedztwa, wymieniają „listy krawędzi” jako trzeci typ reprezentacji grafu. Listę krawędzi można zinterpretować jako listę „obiektów krawędziowych”, takich jak te w odpowiedzi Thomasa „obiekty i wskaźniki”.

Zaleta: możemy przechowywać więcej informacji o krawędzi (o której wspomniał Michał)

Wada: jest to bardzo powolna struktura danych do pracy z:

• Wyszukaj krawędź: O (log e)
• Usuń krawędź: O (e)
• Znajdź wszystkie węzły sąsiadujące z danym węzłem: O (e)
• Sprawdź, czy istnieje ścieżka między dwoma węzłami: O (e ^ 2)

e = liczba krawędzi