Rodzaje grafów w strukturze danych z przykładami
Sara Chen
Wykres to nieliniowa struktura danych składająca się z wierzchołków i krawędzi. Wierzchołki zawierają informacje lub dane, a krawędzie działają jako połączenie pomiędzy parą wierzchołków.
Wykresy mogą być wielu typów, w zależności od położenia węzłów i krawędzi. Oto kilka ważnych typów wykresów:
Kierowany wykres
Krawędzie grafu skierowanego zawierają strzałki oznaczające kierunek. Strzałka określa, gdzie skierowana jest krawędź lub gdzie się ona kończy.
Oto przykład grafu skierowanego.
- Możemy przejść z węzła A do D.
- Nie możemy jednak przejść z węzła D do węzła A, ponieważ krawędzie wskazują z A do D.
- Ponieważ graf nie ma wag, podróż z wierzchołka A do D będzie kosztować tyle samo, co podróż z D do F.
Wykres nieskierowany
Graf nieskierowany zawiera krawędzie bez wskaźników. Oznacza to, że możemy podróżować odwrotnie pomiędzy dwoma wierzchołkami.
Oto prosty przykład grafu nieskierowanego.
Na powyższym wykresie
- Możemy przejść z punktu A do B
- Możemy także przejść z B do A
- Krawędzie nie zawierają kierunków.
To przykład grafu nieskierowanego mającego skończoną liczbę wierzchołków i krawędzi bez wag.
Wykres ważony
Wykres zawierający wagi lub koszty na krawędziach nazywany jest wykresem ważonym. Wartość liczbowa zazwyczaj reprezentuje koszt przeniesienia z jednego wierzchołka do drugiego. Zarówno graf skierowany, jak i nieskierowany mogą mieć wagi na krawędziach.
Oto przykład wykresu ważonego (skierowanego).
- A do B, jest krawędź, a waga wynosi 5, co oznacza, że przejście z A do B będzie nas kosztować 5.
- Punkt do B, ale na tym wykresie B nie ma bezpośredniej przewagi nad A. Zatem nie możemy podróżować z B do A.
- Jeśli jednak chcemy przejść z punktu A do F, istnieje wiele ścieżek. Ścieżki to ADF, ABF. ADF będzie kosztować (10+11) lub 21.
- Tutaj ścieżka ABF będzie kosztować (5+15) lub 20. Tutaj dodajemy wagę każdej krawędzi na ścieżce.
Oto przykład grafu nieskierowanego z wagami:
Tutaj krawędź ma wagę, ale nie ma kierunku. Oznacza to, że podróż z wierzchołka A do D będzie kosztować 10 i odwrotnie.
Wykres dwukierunkowy
Wykresy dwukierunkowe i nieskierowane mają wspólną właściwość. To jest
- Generalnie graf nieskierowany może mieć jedną krawędź pomiędzy dwoma wierzchołkami.
Na przykład:
- Tutaj przejście z A do D lub z D do A będzie kosztować 10.
- W grafie dwukierunkowym możemy mieć dwie krawędzie pomiędzy dwoma wierzchołkami.
Oto przykład:
Podróż z A do D będzie nas kosztować 17, ale podróż z D do A będzie nas kosztować 12. Zatem nie możemy przypisać dwóch różnych wag, jeśli jest to graf nieskierowany.
Nieskończony wykres
Wykres będzie zawierał nieskończoną liczbę krawędzi i węzłów. Jeśli graf jest nieskończony i jest również grafem spójnym, to będzie zawierał także nieskończoną liczbę krawędzi. W tym przypadku wydłużone krawędzie oznaczają, że więcej krawędzi może być połączonych z tymi węzłami za pomocą krawędzi.
Oto przykład nieskończonego wykresu:
Wykres zerowy
Wykres zerowy zawiera tylko węzły lub wierzchołki, ale bez krawędzi. Jeśli dany graf G = (V, E), gdzie V to wierzchołki, a E to krawędzie, będzie on pusty, jeśli liczba krawędzi E będzie wynosić zero.
Oto przykład wykresu zerowego:
Trywialny wykres
Strukturę danych wykresu uważa się za trywialną, jeśli występuje tylko jeden wierzchołek lub węzeł bez krawędzi.
Oto przykład trywialnego wykresu:
Wielu wykres
Wykres nazywa się multigrafem, gdy pomiędzy dwoma wierzchołkami występuje wiele krawędzi lub gdy wierzchołek ma pętlę. Termin „pętla” w strukturze danych wykresu oznacza krawędź wskazującą na ten sam węzeł lub wierzchołek. Multigraf może być skierowany lub nieskierowany.
Oto przykład multigrafu:
Istnieją dwie krawędzie od B do A. Ponadto wierzchołek E ma pętlę własną. Powyższy wykres jest grafem skierowanym, bez wag na krawędziach.
Kompletny wykres
Graf jest kompletny, jeśli każdy wierzchołek ma skierowane lub nieskierowane krawędzie ze wszystkimi pozostałymi wierzchołkami.
Załóżmy, że istnieje całkowita liczba V wierzchołków, a każdy wierzchołek ma dokładnie krawędzie V-1. Następnie ten wykres będzie nazywany wykresem pełnym. W tego typu grafach każdy wierzchołek jest połączony ze wszystkimi innymi wierzchołkami poprzez krawędzie.
Oto przykład pełnego wykresu z pięcioma wierzchołkami:
Na obrazku widać, że całkowita liczba węzłów wynosi pięć, a wszystkie węzły mają dokładnie cztery krawędzie.
Połączony wykres
Wykres nazywany jest grafem spójnym, jeśli zaczynamy od węzła lub wierzchołka i przechodzimy przez wszystkie węzły od węzła początkowego. W tym celu pomiędzy każdą parą węzłów lub wierzchołków powinna znajdować się co najmniej jedna krawędź.
Oto przykład połączonego wykresu:
Oto wyjaśnienie powyższego „przykładowego pełnego wykresu” Wykres:
- Zakładając, że nie ma krawędzi pomiędzy C i F, nie możemy podróżować z A do G. Jednakże krawędź C do F umożliwia nam podróż z danego węzła do dowolnego węzła.
- Graf kompletny jest grafem spójnym, ponieważ możemy przejść od węzła do dowolnego innego węzła na danym grafie.
Wykres cykliczny
Graf nazywamy cyklicznym, jeśli występuje na nim jeden lub więcej cykli.
Oto przykład wykresu cyklicznego:
Tutaj wierzchołki A, B i C tworzą cykl.
Wykres może zawierać wiele cykli.
Skierowany graf acykliczny (DAG)
Wykres nazywa się skierowanym grafem acyklicznym lub DAG, jeśli na wykresie nie ma cykli. DAG jest ważny podczas wykonywania Sortowanie topologiczne lub znalezienie zlecenia wykonania. DAG jest również ważny przy tworzeniu systemów planowania lub skanowania zależności zasobów itp. Jednakże powyższy wykres nie zawiera żadnego cyklu.
Oto prosty przykład skierowanego grafu acyklicznego (DAG):
Wykres cyklu
Wykres cykliczny to nie to samo, co wykres cykliczny. Na wykresie cyklicznym każdy węzeł będzie miał dokładnie dwie połączone krawędzie, co oznacza, że każdy węzeł będzie miał dokładnie dwa stopnie.
Oto przykład wykresu cyklu:
Wykres dwudzielny
Te rodzaje Wykresy to specjalne rodzaje grafów, w których wierzchołki są przypisane do dwóch zbiorów.
Wykres dwustronny musi spełniać zasadę:
- Dwa zestawy wierzchołków powinny być różne, co oznacza, że wszystkie wierzchołki muszą zostać podzielone na dwie grupy lub zbiory.
- Ten sam zestaw Wierzchołki nie powinny tworzyć żadnych krawędzi.
Wykres Eulera
Grafowe struktury danych są uważane za graf Eulera, jeśli wszystkie wierzchołki mają stopień parzysty. Termin stopień wierzchołków oznacza liczbę krawędzi wskazujących lub wychodzących z określonego wierzchołka.
Oto przykład wykresu Eulera:
Wszystkie wierzchołki mają parzyste stopnie. Wierzchołki A, D, E i H mają dwa stopnie. Tutaj węzeł C ma cztery stopnie, co jest parzyste.
Wykres Hamiltona
Wykres Hamiltona to graf łączący, na którym można odwiedzić wszystkie wierzchołki danego wierzchołka bez konieczności ponownego odwiedzania tego samego węzła lub używania tej samej krawędzi. Ten rodzaj połączonego wykresu znany jest jako „wykres Hamiltona”. Ścieżka, którą odwiedzasz, aby sprawdzić, czy dany wykres jest wykresem Hamiltona, czy nie, jest nazywana ścieżką Hamiltona.
Oto prosty przykładowy wykres Hamiltona:
Na tym obrazku możemy odwiedzić wszystkie wierzchołki dowolnego węzła powyższego wykresu. Jedna ze ścieżek może być ADCHBE. Można także znaleźć cykl Hamiltona. Cykl Hamiltona zaczyna się i kończy w tym samym wierzchołku. Zatem cykl Hamiltona będzie ADCHBEA.
