Porównując obiekt wykres reprezentacja do listy przylegania i matrycy reprezentacji dla

Question

Jestem obecnie po poradę Steve Yegge w sprawie przygotowania do technicznego wywiadzie Programowanie: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

W swojej sekcji na wykresach, stwierdza:

Nie są trzy podstawowe sposoby, aby reprezentować wykres w pamięci (obiekty i wskaźniki, macierz i przynależność ) i powinieneś zapoznać się z każdą reprezentacją i jego zaletami i wadami.

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

Po prostu myślę o tym, sam mogę się o tym przekonać, ale chciałbym się upewnić, że nie przegapiłem czegoś ważnego. Jeśli ktoś mógłby opisać to w sposób kompleksowy, lub wskazać mi źródło, które to robi, bardzo bym to docenił.

Answer 1

Obiekty i wskaźniki są w większości takie same jak lista przyległości, przynajmniej w celu porównania algorytmów wykorzystujących te reprezentacje.

Porównaj

struct Node { 
    Node *neighbours[]; 
}; 

z

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

można łatwo skonstruować listę sąsiadów on-the-fly w tym ostatnim przypadku, jeżeli jest łatwiej pracować niż wymienionych wskaźników.

Answer 2

obiektów i wskaźniki

Są to tylko podstawowe datastructures jak Hammar powiedział w drugiej odpowiedzi, w Java byś reprezentować ten z klas takich jak krawędzie i wierzchołki. Na przykład krawędź łączy dwa wierzchołki i może być skierowana lub nieukierunkowana i może zawierać wagę. Werteks może mieć identyfikator, nazwę itp. Zwykle oba mają dodatkowe właściwości. Więc można skonstruować swój wykres z nich 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 stosowany do implementacji obiektowego, ponieważ jest bardziej czytelny i wygodny dla użytkowników obiektowe).

matrycy

macierz jest tylko prosta 2 wymiarową macierz. Zakładając, że vertex ID użytkownika, które mogą być reprezentowane jako int tablicy tak:

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 

ten jest powszechnie stosowany do gęstych wykresach, gdzie dostęp do indeksu jest konieczne. Za pomocą tego możesz reprezentować un/reżyserowaną i ważoną strukturę.

lista sąsiedztwa

To jest tylko prosty mix datastructure, zwykle zaimplementować to przy użyciu HashMap<Vertex, List<Vertex>>.Podobny używany może być HashMultimap w Guava.

To podejście jest fajne, ponieważ masz O (1) (amortyzowane) wyszukiwanie wierzchołków i zwraca mi listę wszystkich sąsiednich wierzchołków do tego konkretnego wierzchołka, którego wymagał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 

ten jest wykorzystywany do reprezentowania rozrzedzone wykresy, jeśli ubiegasz się w Google, należy wiedzieć, że webgraph jest rzadki. Możesz sobie z nimi radzić w bardziej skalowalny sposób, korzystając z BigTable.

Oh i BTW, here jest bardzo dobre podsumowanie tego postu z fantazyjnych zdjęć;)

Answer 3

Advantage reprezentacji obiektu (incidence list) jest to, że dwa sąsiednie wierzchołki podziela tą instancję krawędzi. Ułatwia to manipulowanie przy niekierowanych danych krawędzi (długość, koszt, przepływ lub kierunek). Jednak używa dodatkowej pamięci do wskaźników.

Answer 4

Innym dobrym źródłem: Khan Academy - "Representing Graphs"

Poza listy przylegania i macierz sąsiedztwa, wymieniają „edge” list jako 3rd rodzaju reprezentacji grafów. Listę krawędzi można interpretować jako listę "obiektów krawędziowych", takich jak te w odpowiedziach "obiektów i wskaźników" Thomasa.

Advantage: Możemy zapisać więcej informacji na temat krawędzi (wspomniany Michał)

Wada: Jest to bardzo powolny struktura danych do pracy z:

• Lookup krawędzi: O (log e)
• Usuwanie krawędź: o (e)
• Znajdź wszystkich węzłów sąsiadujących z danym węzłem: o (e)
• Ustalenie, czy istnieje ścieżka między dwoma węzłami: o (e^2)

E = liczba krawędzi