obiektu i wskaźnik Wykres reprezentacji dla

Question

Ciągle widzę wszędzie, że są 3 sposoby przedstawiają wykresy:

1. obiektów i wskaźniki
2. macierz sąsiedztwa
3. list sąsiedztwa

Jednakże, po prostu zwykły nie rozumiem, czym są te obiekty i reprezentacje wskaźników - jednak każdy rekruter i wiele blogów cytują blog Steve Yegge's, że są one rzeczywiście oddzielną reprezentacją.

This widely accepted answer bardzo podobny pytanie wydaje się sugerować, że te same struktury wierzchołków ma żadnych wewnętrznych odnośniki do pozostałych wierzchołków, a zamiast wszystkie krawędzie są reprezentowane przez struktury brzegowych, które zawierają wskaźniki do sąsiednich wierzchołków.

W jaki sposób ta reprezentacja zapewnia jakąkolwiek dostrzegalną przewagę analityczną w każdym scenariuszu?

Answer 1

Z mojej głowy mam nadzieję, że fakty są prawidłowe.

W ujęciu koncepcyjnym wykres próbuje przedstawić sposób, w jaki zestaw węzłów (lub wierzchołków) jest powiązany (połączony) ze sobą (za pośrednictwem krawędzi). Jednak w rzeczywistym urządzeniu fizycznym (pamięci) mamy ciągły szereg komórek pamięci.

Tak więc, aby przedstawić wykres, możemy wybrać użycie macierzy. W tym przypadku używamy indeksu wierzchołków jako wiersza i kolumny, a wpis ma wartość 1, jeśli wierzchołki sąsiadują ze sobą, 0 w przeciwnym razie.

Można również reprezentować wykres, przypisując obiekt do reprezentowania węzła/wierzchołka, który wskazuje na listę wszystkich węzłów, które są do niego przyległe.

Reprezentacja macierzy daje przewagę, gdy wykres jest gęsty, co oznacza, że ​​większość węzłów/wierzchołków jest połączonych ze sobą. Dzieje się tak, ponieważ w takich przypadkach, przy użyciu wpisu macierzy, oszczędzamy nam konieczności przydzielania dodatkowego wskaźnika (który potrzebuje pamięci rozmiaru słowa) dla każdego połączenia.

Dla uproszczonego wykresu podejście do listy jest lepsze, ponieważ nie trzeba uwzględniać pozycji 0, gdy nie ma połączenia między wierzchołkami.

Mam nadzieję, że to pomaga.

Answer 2

Na razie trudno mi znaleźć typowe "algorytmy wykresów" pro w.r.t. Ale na pewno możliwe jest przedstawienie wykresu z obiektami i wskaźnikami i bardzo naturalną rzeczą do zrobienia, jeśli uważasz, że jest to reprezentacja czegoś, co właśnie rysujesz na tablicy.

Pomyśl o scenariuszu, w którym chcesz połączyć węzły wykresu w określonej kolejności. Węzły mają ładunki zawierające dane domeny, sama struktura wykresu nie jest podstawowym elementem programu.

Oczywiście, możesz aktualizować swoje listy/macierze dla każdej operacji, ale biorąc pod uwagę strukturę "obiektów i wskaźników", możesz scalić lokalnie. Ponadto, jeśli węzły mają ładunek, oznacza to, że listy/macierz będą zawierały identyfikatory węzłów, które identyfikują rzeczywiste obiekty węzłów. Kombinacja oznaczałaby aktualizację reprezentacji wykresu, śledzenie identyfikatorów węzłów i rzeczywiste przetwarzanie. Może się wydawać, że bardziej intuicyjnie działa się na rzeczywistych obiektach węzłów i po prostu usuwa wskaźniki podczas zwijania sąsiada (i usuwania tego węzła).

Poza tym, istnieje więcej sposobów do reprezentowania wykresu:

• Np podobnie jak trójek, takich jak Turle lub jako reprezentacja przesunięcia na węzeł w macierzy krawędzi), np. this Boost data structure (disclaimer: nie testowałem połączoną realizację ja)
• itp

Answer 3

Oto sposób używam do tworzenia wykresu z tym pojęciem:

#include <vector> 

class Node 
{ 
    public: 
     Node(); 
     void setLink(Node *n); // *n as argument to pass the address of the node 
     virtual ~Node(void); 
    private: 
     vector<Node*> m_links; 
}; 

a funkcja odpowiedzialna za tworzenie powiązania między wierzchołkami to:

void Node::setLink(Node *n) 
{ 
    m_links.push_back(n); 
}