Struktura danych wykresu i Algorithms (Przykład)
Sara Chen
⚡ Inteligentne podsumowanie
Struktura danych grafu to nieliniowy zbiór wierzchołków i krawędzi, gdzie każda krawędź łączy parę wierzchołków. Grafy modelują rzeczywiste sieci, takie jak mapy, połączenia społecznościowe i strony internetowe, i obsługują wiele zaawansowanych algorytmów.
Co to jest wykres w strukturze danych?
Graf to nieliniowa struktura danych składająca się z wierzchołków i krawędzi. Wierzchołki zawierają informacje lub dane, a krawędzie pełnią funkcję łącznika między parami wierzchołków.
Służy do rozwiązywania rzeczywistych problemów, takich jak znajdowanie najlepszej trasy do miejsca docelowego oraz trasy dla sieci telekomunikacyjnych i społecznościowych. Użytkownicy są traktowani jako węzły w grafie, a przewody to krawędzie łączące użytkowników.
Jeśli krawędzie są reprezentowane jako E, a wierzchołki jako V, wówczas graf G można zapisać jako zbiór wierzchołków i krawędzi, np. G (V, E).
Przykład wykresu w strukturze danych
Oto prosty przykład struktury danych grafu:
To prosty graf nieskierowany (jeden rodzaj grafu). Tutaj zbiór wierzchołków to: {A, B, C, D, E, F}. Dwa wierzchołki tworzą krawędź. Na przykład, A i B są połączone krawędzią. Jednak A i F nie są połączone żadną krawędzią.
Terminologie dotyczące grafów w strukturze danych
Poniżej przedstawiono kilka ważnych terminów używanych w strukturze danych grafu:
| Semestr | OPIS |
|---|---|
| Wierzchołek | Każdy element danych nazywany jest wierzchołkiem lub węzłem. Na powyższym obrazku A, B, C, D i E to wierzchołki. |
| Krawędź (łuk) | Łączniki między dwoma węzłami lub wierzchołkami nazywane są krawędzią (łukiem). Mają dwa końce i są reprezentowane przez (wierzchołek początkowy, wierzchołek końcowy). |
| Nieukierunkowana krawędź | Jest to krawędź dwukierunkowa. |
| Wyreżyserowany Edge | Jest to krawędź jednokierunkowa. |
| Ważona krawędź | Krawędź z przypisaną wartością. |
| Stopień | W grafie liczbę krawędzi połączonych z wierzchołkiem nazywa się stopniem. |
| stopień | Całkowita liczba przychodzących krawędzi połączonych z wierzchołkiem. |
| stopień naukowy | Całkowita liczba wychodzących krawędzi połączonych z wierzchołkiem. |
| Pętla własna | Krawędź nazywa się pętlą własną, jeśli jej dwa punkty końcowe pokrywają się. |
| Przyleganie | Wierzchołki uznaje się za sąsiadujące, jeżeli łączy je krawędź. |
Rodzaje grafów w strukturze danych
Oto lista najczęściej spotykanych rodzaje grafów w strukturze danych:
- Kierowany wykres
- Wykres nieskierowany
- Wykres ważony
- Wykres dwukierunkowy
- Nieskończony wykres
- Wykres zerowy
- Trywialny wykres
- Wielu wykres
- Kompletny wykres
- Połączony wykres
- Wykres cykliczny
- Skierowany graf acykliczny (DAG)
- Wykres cyklu
- Wykres dwudzielny
- Wykres Eulera
- Wykres Hamiltona
Jak przedstawić graf w strukturze danych?
Graf jest zazwyczaj przechowywany w pamięci przy użyciu jednej z dwóch reprezentacji. Wybór wpływa na ilość pamięci wykorzystywanej przez graf oraz szybkość wykonywania typowych operacji.
- Macierz sąsiedztwa: Dwuwymiarowa tablica V × V, w której komórka [i][j] ma wartość 1 (lub wagę krawędzi), jeśli istnieje krawędź między wierzchołkiem i a wierzchołkiem j, a 0 w przeciwnym wypadku. Umożliwia wyszukiwanie krawędzi z częstotliwością O(1), ale wykorzystuje przestrzeń O(V²), co czyni ją najlepszą dla gęstych grafów.
- Lista sąsiedztwa: Tablica list, w której każdy wierzchołek przechowuje listę sąsiednich wierzchołków. Wykorzystuje przestrzeń O(V + E) i jest wydajna w przypadku grafów rzadkich, dlatego korzysta z niej większość grafów rzeczywistych.
Więcej na ten temat możesz przeczytać w lista sąsiedztwa i reprezentacja macierzowa grafu poradnik.
Zastosowania struktury danych grafowych
Graf ma wiele zastosowań. Istnieje wiele algorytmów wykorzystujących grafy. Oto niektóre z zastosowań grafu:
- Google Mapy wykorzystują wykresy do znajdowania skrzyżowań dwóch dróg i obliczania odległości między dwoma lokalizacjami. Na przykład: Dijkstra, w celu znalezienia najkrótszej odległości między lokalizacją źródłową i docelową.
- Facebook wykorzystuje grafy do wyszukiwania wspólnych znajomych użytkowników. Jego algorytm traktuje każdego użytkownika jako węzeł grafu.
- Do alokacji zasobów używany jest DAG (Directed Acyclic Graph), który sprawdza zależność zasobów.
- Google Wyszukiwarka używa wykresów do ustalania rankingu stron internetowych.
- Mapaping Urządzenie wykorzystuje strukturę danych grafu.
- A Router a jego protokół wykorzystuje Graf do poznania ścieżki do celu.
