Rodzaje grafów w strukturze danych z przykładami

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.

Grafy mogą być różnych typów, w zależności od położenia węzłów i krawędzi. Oto kilka ważnych typów grafów:

Kierowany wykres

Krawędzie grafu skierowanego zawierają strzałki oznaczające kierunek. Strzałka określa, gdzie krawędź jest skierowana lub gdzie się kończy. Oto przykład grafu skierowanego.

Kierowany wykres

• Możemy przejść z węzła A do D.
• Nie możemy jednak przejść od węzła D do węzła A, ponieważ krawędź wskazuje od 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 przemieszczać się w drugą stronę między dwoma wierzchołkami. Oto prosty przykład grafu nieskierowanego.

Wykres nieskierowany

Na powyższym wykresie

• Możemy przejść z punktu A do punktu B.
• Możemy również przejść z B do A.
• Krawędzie nie zawierają kierunków.

Jest to przykład grafu nieskierowanego posiadającego skończoną liczbę wierzchołków i krawędzi bez żadnych wag.

Wykres ważony

Graf, który zawiera wagi lub koszty na krawędziach, nazywa się grafem ważonym. Wartość liczbowa zazwyczaj reprezentuje koszt przeniesienia z jednego wierzchołka do drugiego. Zarówno grafy skierowane, jak i nieskierowane mogą mieć wagi na krawędziach. Oto przykład grafu ważonego (skierowanego).

Wykres skierowany z wagą

• Z A do B istnieje krawędź, a waga wynosi 5, co oznacza, że ​​przejście z A do B będzie nas kosztowało 5.
• A wskazuje na B, ale na tym wykresie B nie ma bezpośredniej przewagi nad A. Nie możemy więc podróżować z B do A.
• Jeśli jednak chcemy przejść z A do F, istnieje wiele ścieżek. Ścieżki to ADF i ABF. Koszt ADF wyniesie (10+11) lub 21.
• Tutaj ścieżka ABF będzie kosztować (5+15) czyli 20. Tutaj dodajemy wagę każdej krawędzi na ścieżce.

Oto przykład grafu nieskierowanego z wagami:

Wykres nieskierowany z wagą

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

Grafy dwukierunkowe i nieskierowane mają wspólną cechę:

• Zasadniczo 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:

Wykres dwukierunkowy

Podróż z A do D będzie nas kosztować 17, ale podróż z D do A będzie nas kosztować 12. Dlatego nie możemy przypisać dwóch różnych wag, jeśli jest to graf nieskierowany.

Nieskończony wykres

Graf będzie zawierał nieskończoną liczbę krawędzi i węzłów. Jeśli graf jest nieskończony i jednocześnie spójny, to będzie zawierał również nieskończoną liczbę krawędzi. W tym przypadku rozszerzone krawędzie oznaczają, że więcej krawędzi może być połączonych z tymi węzłami za pośrednictwem krawędzi. Oto przykład grafu nieskończonego:

Nieskończony wykres

Wykres zerowy

Graf zerowy zawiera tylko węzły lub wierzchołki, ale bez krawędzi. Jeśli dany jest graf G = (V, E), gdzie V to wierzchołki, a E to krawędzie, będzie on zerowy, jeśli liczba krawędzi E będzie równa zero. Oto przykład grafu zerowego:

Wykres zerowy

Trywialny wykres

Strukturę danych grafu uważa się za trywialną, jeśli występuje w niej tylko jeden wierzchołek lub węzeł bez krawędzi. Oto przykład grafu trywialnego:

Wielu wykres

Graf nazywany jest multigrafem, gdy między dwoma wierzchołkami występuje wiele krawędzi lub gdy wierzchołek ma pętlę. Termin „pętla” w strukturze danych grafu 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. Co więcej, wierzchołek E ma pętlę własną. Powyższy graf jest grafem skierowanym bez wag na krawędziach.

Kompletny wykres

Graf jest kompletny, jeśli każdy wierzchołek ma krawędzie skierowane lub nieskierowane ze wszystkimi pozostałymi wierzchołkami. Załóżmy, że istnieje V wierzchołków i każdy wierzchołek ma dokładnie V-1 krawędzi. Wówczas taki graf będzie nazywany grafem kompletnym. W tym typie grafu każdy wierzchołek jest połączony ze wszystkimi pozostałymi wierzchołkami za pomocą krawędzi. Oto przykład grafu kompletnego z pięcioma wierzchołkami:

Na obrazku widać, że całkowita liczba węzłów wynosi pięć i każdy z nich ma dokładnie cztery krawędzie.

Połączony wykres

Graf nazywa się grafem spójnym, jeśli zaczynamy od węzła lub wierzchołka i możemy przejść do wszystkich węzłów od węzła początkowego. W tym celu powinna istnieć co najmniej jedna krawędź między każdą parą węzłów lub wierzchołków. Oto przykład grafu spójnego:

Oto wyjaśnienie powyższego spójnego grafu:

• Zakładając, że nie ma krawędzi pomiędzy C i F, nie możemy przejść z A do G. Jednakże krawędź C do F umożliwia nam przejście 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 nazywa się cyklicznym, jeśli zawiera jeden lub więcej cykli. Oto przykład grafu cyklicznego:

W tym przypadku wierzchołki A, B i C tworzą cykl. Wewnątrz grafu może znajdować się wiele cykli.

Skierowany graf acykliczny (DAG)

Graf nazywa się skierowanym grafem acyklicznym lub DAG, jeśli w grafie nie ma cykli. DAG jest ważny podczas wykonywania Sortowanie topologiczne lub znajdowanie kolejności wykonywania. DAG jest również ważny przy tworzeniu systemów harmonogramowania, skanowaniu zależności zasobów itp. Jednak powyższy graf nie zawiera żadnego cyklu. Oto prosty przykład skierowanego grafu acyklicznego (DAG):

Wykres cyklu

Graf cyklu to nie to samo, co graf cykliczny. W grafie cyklu 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 grafu cyklu:

Wykres dwudzielny

Te rodzaje Wykresy Grafy dwudzielne to specjalne rodzaje grafów, w których wierzchołki są przypisane do dwóch zbiorów. Graf dwudzielny musi spełniać następującą zasadę:

• Dwa zbiory wierzchołków muszą być różne, co oznacza, że ​​wszystkie wierzchołki muszą być podzielone na dwie grupy lub zbiory.
• Takie same wierzchołki nie powinny tworzyć żadnych krawędzi.

Wykres Eulera

Strukturę danych grafu uważa się za graf Eulera, jeśli wszystkie wierzchołki mają stopień parzysty. Termin stopień wierzchołków oznacza liczbę krawędzi wskazujących na dany wierzchołek lub od niego odchodzących. Oto przykład grafu Eulera:

Wszystkie wierzchołki mają parzyste stopnie. Wierzchołki A, D, E i H mają dwa stopnie. W tym przypadku węzeł C ma cztery stopnie, co jest liczbą parzystą.

Wykres Hamiltona

Graf Hamiltona to graf spójny, w którym można przejść do wszystkich wierzchołków z danego wierzchołka bez ponownego odwiedzania tego samego węzła lub używania tej samej krawędzi. Ten rodzaj grafu spójnego znany jest jako „graf Hamiltona”. Ścieżka, którą należy przejść, aby sprawdzić, czy dany graf jest grafem Hamiltona, nazywana jest ścieżką Hamiltona. Oto prosty przykład grafu 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 również znaleźć cykl Hamiltona. Cykl Hamiltona zaczyna się i kończy w tym samym wierzchołku. Zatem cykl Hamiltona będzie… ADCHBEA.

FAQ