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.
źródło
Odpowiedzi:
obiekty i wskaźniki
To tylko podstawowe struktury danych, jak Hammar powiedział w drugiej odpowiedzi, w
Java
któ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, jakTakie 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:
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ćHashMultimap
w 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.
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;)
źródło
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.HashTable
użycie. Nie ma więc potrzeby czepiać się małego, stałego narzutu alfa, który można zaniedbać.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ć
z
W tym drugim przypadku możesz łatwo utworzyć listę sąsiadów w locie, jeśli jest łatwiejsza w pracy niż nazwane wskaźniki.
źródło
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.
źródło
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:
e = liczba krawędzi
źródło