Jakiś lista sąsiedztwa to struktura danych używana do reprezentowania grafu, w której każdy węzeł grafu przechowuje listę sąsiadujących wierzchołków.
Grafowa reprezentacja grafu skierowanego do listy sąsiedztwa
Charakterystyka listy sąsiedztwa:
- Rozmiar macierzy zależy od liczby węzłów w sieci.
- Liczbę krawędzi grafu można łatwo obliczyć.
- Lista sąsiedztwa to a postrzępiony układ .
Jak zbudować listę sąsiedztwa?
Stworzenie listy sąsiedztwa dla grafu jest bardzo łatwe i proste. Poniżej przedstawiono pewne kroki, które należy wykonać:
- Utwórz tablicę połączonych list rozmiarów N , gdzie N jest liczbą wierzchołków grafu.
- Utwórz połączoną listę sąsiadujących wierzchołków dla każdego wierzchołka na wykresie.
- Dla każdej krawędzi (ty, v) na wykresie dodaj W do powiązanej listy W , i dodaj W do powiązanej listy W jeśli wykres jest nieskierowany, w przeciwnym razie dodaj W do listy W jeśli jest kierowany z W Do W . (W przypadku wykresów ważonych przechowuj masę wraz z połączeniami).
Zastosowania listy sąsiedztwa:
- Algorytm Dijkstry , Wyszukiwanie wszerz , I Pierwsze wyszukiwanie w głębi używać list sąsiedztwa do reprezentowania grafów.
- Przetwarzanie obrazu : Listy sąsiedztwa mogą służyć do reprezentowania relacji sąsiedztwa pomiędzy pikselami na obrazku.
- Produkcja gier : Listy te mogą służyć do przechowywania informacji o połączeniach pomiędzy różnymi obszarami lub poziomami. Twórcy gier używają wykresów do przedstawienia map lub poziomów gier.
Zalety korzystania z listy sąsiedztwa:
- Lista sąsiedztwa jest prosta i łatwa do zrozumienia.
- Dodawanie lub usuwanie krawędzi z wykresu jest szybkie i łatwe.
Wady korzystania z listy sąsiedztwa:
- Na listach sąsiedztwa dostęp do krawędzi może zająć więcej czasu niż w przypadku macierzy sąsiedztwa.
- Wymaga więcej pamięci niż macierz sąsiedztwa dla gęstych grafów.
Co jeszcze możesz przeczytać?
- Znaczenie i definicja macierzy sąsiedztwa w DSA
- Dodawanie i usuwanie krawędzi w reprezentacji wykresu na liście sąsiedztwa
- Konwertuj macierz sąsiedztwa na reprezentację wykresu na podstawie listy sąsiedztwa
- Konwertuj listę sąsiedztwa na reprezentację wykresu w postaci macierzy sąsiedztwa
- Porównanie pomiędzy listą sąsiedztwa a reprezentacją wykresu w postaci macierzy sąsiedztwa