Rodzaje wykresów w strukturze danych i zastosowaniach

Wstęp

Graf to nieliniowa struktura zawierająca węzły i krawędzie. Może zawierać skończony lub nieskończony zestaw węzłów utrzymywanych przez krawędź łączącą parę węzłów. Struktury danych są istotną częścią każdej koncepcji kodowania; w związku z tym dobre zrozumienie różnych typów grafów w strukturach danych może pomóc w rozwiązywaniu złożonych rzeczywistych problemów.

W dzisiejszym świecie dane to potęga. Dlatego efektywne organizowanie danych w celu łatwego dostępu jest niezbędne dla każdego programisty. Znajomość struktur danych i ich różnorodnych wykresów zwiększa Twoje umiejętności kodowania, aby rozwiązywać rzeczywiste problemy i skutecznie dostarczać ich rozwiązania.

Naucz się analizy danych, aby zyskać przewagę nad konkurencją

Przyjrzyjmy się różnym typom grafów powszechnie używanych w strukturach danych i temu, jak są one stosowane w prawdziwym życiu.

Rodzaje wykresów w strukturach danych

Struktura danych jest praktycznym standardem przechowywania danych we wszystkich językach, takim jak struktura danych wykresu Pythona lub struktura danych wykresu java. Opanowanie wszystkich rodzajów wykresów powinno być priorytetem dla każdego, kto chce studiować struktury danych. Ponieważ teoria grafów ma wiele zastosowań w życiu codziennym, stają się one niezbędne w strukturach danych.

Poniżej wymieniono różne typy wykresów w strukturach danych :

1. Wykres zerowy

Jak sama nazwa wskazuje, wykres zerowy jest pusty; innymi słowy, jest to wykres bez krawędzi. Składa się tylko z izolowanych wierzchołków grafu z pustym zestawem krawędzi.

2. Wykres skończony

Jeśli liczba krawędzi i węzłów w grafie składa się ze skończonej liczby, to graf ten nazywamy grafem skończonym.

3. Nieskończony wykres

Jeśli nie można przypisać skończonej liczby do liczby węzłów i liczby krawędzi grafu, graf ten jest znany jako graf nieskończony. Grafy nieskończone są niepoliczalne, co oznacza, że ​​nie można policzyć węzłów ani krawędzi w tego typu grafach.

4. Prosty wykres

O grafie mówimy, że jest prosty, gdy między parą wierzchołków jest tylko jedna krawędź. Zatem dwa węzły są połączone jedną krawędzią na grafie, co pozwala zidentyfikować określony związek między nimi.

5. Wielu wykresów

Jeśli para węzłów jest połączona z wieloma krawędziami w grafie, wówczas graf jest znany jako multigraf. Multiwykres nie składa się z pętli własnych. Istnieją dwa rodzaje krawędzi, które mogą istnieć w multigrafie. Oni są:

• Krawędzie równoległe

Krawędzie, które biegną równolegle, jak dwie równoległe drogi biegnące od jednego źródła do tego samego celu, nazywane są równoległymi krawędziami.

• Pętla

Jest to krawędź, której wierzchołki źródłowy i docelowy są takie same.

Sprawdź nasze amerykańskie programy nauki o danych

6. Graf skierowany

Mówimy, że graf jest skierowany, jeśli wszystkie krawędzie między dwoma węzłami lub wierzchołkami mają określony kierunek. Graf skierowany jest również nazywany digrafem. Możemy określić węzeł początkowy i końcowy, patrząc na skierowany graf. Pamiętaj, że wszystkie krawędzie w grafie skierowanym muszą być skierowane, aby można go było nazwać grafem skierowanym.

7. Graf nieskierowany

O grafie mówi się, że jest grafem nieskierowanym, jeśli trudno jest zidentyfikować węzeł początkowy i końcowy, patrząc na jego krawędzie. Podobnie jak graf skierowany, krawędzie muszą być nieskierowane, aby można było go nazwać grafem nieskierowanym.

8. Połączony wykres

Graf spójny to graf, w którym istnieje co najmniej jedna ścieżka między wszystkimi węzłami. Mówiąc prościej, jeśli zaczniesz od węzła w połączonym grafie, powinieneś być w stanie odwiedzić każdy węzeł obecny na grafie. Dlatego dla każdego węzła powinna istnieć co najmniej jedna ścieżka.

9. Odłączony wykres

W grafie tego typu nie istnieje żadna krawędź między parą węzłów lub wierzchołków. Zatem, w przeciwieństwie do grafów połączonych, dotarcie do wszystkich węzłów z dowolnego wierzchołka nie jest możliwe. Jeśli jakakolwiek para wierzchołków nie ma między sobą ścieżki, nazywa się to grafem rozłączonym.

10. Uzupełnij wykres

Graf jest uważany za kompletny tylko wtedy, gdy między każdym węzłem istnieje krawędź, co oznacza, że ​​krawędź połączy wszystkie wierzchołki grafu. Pełny graf o n wierzchołkach oznaczamy jako Kn , a liczba krawędzi w grafie to nC2 .

11. Wykres cykliczny

Wykres powinien mieć co najmniej jeden składnik cykliczny, aby można go było uznać za wykres cykliczny. Przeciwnie, jeśli graf nie zawiera żadnego cyklu, jest uważany za graf acykliczny.

12. Regularny wykres

W grafie regularnym wszystkie wierzchołki powinny mieć ten sam stopień. Stopień węzła można zdefiniować jako liczbę połączonych z nim węzłów. Zatem w regularnym grafie wszystkie węzły powinny być połączone z tą samą liczbą węzłów.

13. Wykres dwudzielny

Aby graf był dwudzielny, powinien spełniać następujące kryteria.

• Graf należy podzielić na zbiory wierzchołków.
• Krawędzie powinny tworzyć się tylko między jedną grupą węzłów po drugiej stronie. Ta reguła zapobiega połączeniu między dwoma wierzchołkami tego samego zestawu węzłów.
• Obie grupy nie powinny mieć między sobą żadnych wspólnych wierzchołków.

Graf spełniający wszystkie powyższe zasady należy uważać za graf dwudzielny.

14. Oznaczony wykres

Krawędzie w grafach mogą być ważone. Ciężar związany z krawędzią można rozumieć jako koszt przejazdu przez tę krawędź. Wartości te mogą opierać się na stałym parametrze i mogą zmieniać się między wykresami. Teraz, jeśli wszystkie krawędzie mają jakąś wagę z nimi związaną, to ten wykres można nazwać grafem z etykietą.

15. Skierowany graf acykliczny

Skierowany graf acykliczny to połączenie grafów skierowanych i acyklicznych, w których skierowane krawędzie grafu nie tworzą żadnej formy cyklu. Przeciwnie, skierowany graf cykliczny to graf ze skierowanymi krawędziami, który tworzy cykl.

Zastosowanie wykresu w strukturze danych

Najbardziej znanym zastosowaniem wykresu w informatyce jest reprezentacja przepływu obliczeń. Niektóre inne znane przypadki użycia wykresów to:

1. Mapy Google

W Mapach Google struktury danych grafów definiują i obliczają system transportowy. Kiedy droga spotyka się z inną drogą i tworzy skrzyżowanie, jest uważana za węzeł, a droga między dwoma takimi węzłami jest traktowana jako krawędź. W związku z tym Mapy Google znajdują najkrótszą i najszybszą drogę do celu, korzystając ze struktury danych wykresu.

2. Facebooka

Facebook używa nieukierunkowanych wykresów do identyfikacji użytkownika i jego znajomych. Każdy użytkownik traktowany jest jako wierzchołki, a połączenia łączące ich jako znajomych to krawędzie sieci. Dzięki algorytmom opartym na strukturze danych grafów Facebook sugeruje „ludzi, których możesz znać” i pokazuje „wspólnych znajomych”.

3. Sieć WWW

World Wide Web jest przykładem skierowanego grafu. Jest to również podstawowa idea stojąca za systemem rankingowym Google. W systemie World Wide Web każda witryna i aplikacja internetowa jest traktowana jako węzeł lub wierzchołki, a łącza z jednej witryny do drugiej są uważane za krawędź.

4. System operacyjny

System operacyjny to popularnie stosowany przypadek wykresów alokacji zasobów, który wykorzystuje każdy proces i zasób jako węzły lub wierzchołki. Krawędzie występują między zasobami a przydzielonym procesem lub między procesem żądającym a żądanymi zasobami. Czasami ten cykl może tworzyć nieskończoną pętlę, inicjując impas.

5. System mapowania

Twój GPS to powszechnie używany przypadek wykresów do lokalizowania pobliskich restauracji, sklepów i miejsc, które wybierasz do wyszukiwania za pomocą tej technologii.

6. MicrosoftExcel

Skierowane wykresy acykliczne lub DAG są używane w programie Microsoft Excel.

7. Algorytm Dijkstry

Algorytm Dijkstry wykorzystuje strukturę danych grafu do identyfikacji najkrótszej ścieżki między dwoma lub w niektórych przypadkach więcej niż dwoma węzłami.

8. Sieci lotów:

Obliczanie zoptymalizowanych sieci lotów to kolejne rzeczywiste zastosowanie struktury danych grafów. Jeśli weźmiemy pod uwagę lotniska jako węzły, a trasy jako krawędzie, dane idealnie pasują do kryteriów grafów. Dlatego za pomocą różnych ulepszonych algorytmów określane są najlepsze trasy między dwoma lotniskami lub węzłami.

Są to różne zastosowania grafów w strukturze danych , stosowane na całym świecie w różnych aplikacjach i systemach do organizowania i utrzymywania ich sprawnego funkcjonowania,

Rozpocznij swoją podróż jako analityk danych

Jeśli chcesz zostać naukowcem danych i taktownie obchodzić się z danymi, korzystając z różnych wykresów, których się nauczyliśmy, zapoznaj się z szeroką gamą kursów nauki danych na upGrad. Jednym z najpopularniejszych kursów jest kurs PG-IIITB dotyczący nauki o danych , doskonały kurs dla początkujących i początkujących naukowców zajmujących się danymi na początek!

Oto, co oferuje kurs.

• 360-stopniowe wsparcie kariery od ekspertów branżowych i mentorów
• Praktyczne doświadczenie z projektami branżowymi i szczegółowe studia przypadków w celu oceny regularnych postępów
• Współpraca z ekspertami ds. nauki o danych we wszystkich sektorach na całym świecie

Możesz także sprawdzić wszystkie inne kursy upGrad dotyczące Data Science .