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

82

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.

jbeard4
źródło
a co z wykresami indukcyjnymi - do której z 3 kategorii należą?
Erik Kaplun,

Odpowiedzi:

94

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;)

Thomas Jungblut
źródło
To podejście jest fajne, ponieważ masz wyszukiwanie wierzchołków O (1), ta złożoność jest nieco błędna, w szczególności jest to O (1 + alfa), gdzie alpha = liczba szczelin w mapie hash / liczba wierzchołków. Dlatego proponuję użyć tablicy zamiast mapy hash
Timofey
@Tim to jest amortyzowane O (1). Twoje obliczenia złożoności są silnie zależne od implementacji. Zobacz javadoc HashMap( docs.oracle.com/javase/7/docs/api/java/util/HashMap.html ) mówi: This implementation provides constant-time performance for the basic operations= O (1) amortyzowane.
Thomas Jungblut,
6
@Tim Myślę, że wszyscy tutaj wiedzą, że dostęp do tablicy jest szybszy niż jakiekolwiek HashTableużycie. Nie ma więc potrzeby czepiać się małego, stałego narzutu alfa, który można zaniedbać.
Thomas Jungblut,
2
Proszę, nie zrozum mnie źle, nie obrażam Cię miła odpowiedź, ale mam przeczucie, że Twoja odpowiedź może być poprawiona, więc czemu o tym nie wspominać :)
Timofey
2
@Tim Dodałem zamortyzowaną notatkę do odpowiedzi. Dzięki.
Thomas Jungblut
7

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.

hammar
źródło
4

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.

Michal Čizmazia
źródło
5
dlaczego istnieje link do reprezentacji listy sąsiedztwa zwanej „listą incydentów”? Prawdopodobnie lepiej jest użyć tego algorytmu.com/index.php/Graph_data_structures#Incidence_List
Timofey
1

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

Chris Leung
źródło