Struktura danych wykresu i Algorithms (Przykład)
Co to jest wykres w strukturze danych?
Wykres to nieliniowa struktura danych składająca się z wierzchołków i krawędzi, przy czym wierzchołki zawierają informacje lub dane, a krawędzie działają jako połączenie między parą wierzchołków.
Służy do rozwiązywania rzeczywistych problemów tekstowych, takich jak znalezienie najlepszej trasy do miejsca docelowego oraz trasy dla sieci telekomunikacyjnych i społecznościowych. Użytkownicy są uważani za węzły na wykresie, 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 wykresu:
Jest 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że A i F nie są połączone żadnymi krawędziami.
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) | Łączące połączenia między dwoma węzłami lub wierzchołkami nazywane są krawędzią (łukiem). Ma dwa końce i jest reprezentowany jako (wierzchołek początkowy, wierzchołek kończący). |
Nieukierunkowana krawędź | Jest to krawędź dwukierunkowa. |
Wyreżyserowany Edge | Jest to krawędź jednokierunkowa. |
Ważona krawędź | Przewaga posiadająca wartość. |
Stopień | Na grafie liczba krawędzi połączonych z wierzchołkiem nazywana jest 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 | Mówi się, że wierzchołki sąsiadują ze sobą, jeśli krawędź jest połączona. |
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
Zastosowania struktury danych grafowych
Graf ma wiele przypadków użycia. Istnieje wiele algorytmów, które często używają Grafów. Oto niektóre z zastosowań Grafu:
- Mapy Google korzystają z wykresów, aby znaleźć skrzyżowanie dwóch dróg i obliczyć odległość między dwiema lokalizacjami.
Na przykład, Dijkstra, aby znaleźć najkrótszą odległość między lokalizacją źródłową a docelową. - Facebook korzysta z wykresów, aby znaleźć 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 (Direct Acycle Graph). Sprawdza zależność zasobów.
- Wyszukiwarka Google wykorzystuje wykresy do tworzenia rankingu stron internetowych.
- Urządzenie mapujące wykorzystuje strukturę danych grafu.
- Router i protokół t wykorzystuje wykres do poznania ścieżki ścieżki docelowej.