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:

Przykład wykresu w strukturze danych

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.