Wykresy w strukturze danych: typy, przechowywanie i przechodzenie

Struktura danych to wydajny sposób organizowania danych w nauce o danych, tak aby można było łatwo uzyskać do nich dostęp i efektywnie wykorzystywać. Istnieje wiele rodzajów baz danych, ale w tym artykule omówiono, dlaczego wykresy odgrywają istotną rolę w zarządzaniu danymi.

Alert spoilera: codziennie używasz wykresów w strukturze danych, aby znaleźć najlepszą trasę do biura, uzyskać sugestie dotyczące lunchu, filmu i zoptymalizować trasę następnego lotu. Brzmi interesująco! Przyjrzyjmy się właściwościom wykresu i jego zastosowaniu.

Najpierw zobaczmy, czym jest wykres? Jest to reprezentacja danych w nieliniowej strukturze składającej się z węzłów (wierzchołków) i krawędzi (lub ścieżek).

Wykres w strukturze danych można określić jako strukturę danych składającą się z danych przechowywanych w wielu grupach krawędzi (ścieżek) i wierzchołków (węzłów), które są ze sobą połączone. Struktura danych wykresu (N, E) jest zbudowana z kolekcji węzłów i krawędzi. Zarówno węzły, jak i wierzchołki muszą być skończone.

W powyższej reprezentacji grafu zbiór węzłów to N={0,1,2,3,4,5,6}a zbiór krawędzi to

G={01,12,23,34,45,05,03}

Teraz przestudiujmy rodzaje wykresów.

Przeczytaj: 10 najlepszych technik wizualizacji danych

Rodzaje wykresów

1. Wykres ważony

Wykresy, których krawędzie lub ścieżki mają wartości. Wszystkie widoczne wartości związane z krawędziami nazywane są wagami. Wartość krawędzi może reprezentować wagę/koszt/długość.

Wartości lub wagi mogą również przedstawiać:

• Odległość pokonywana między dwoma punktami- Np.: Aby znaleźć najkrótszą drogę do biura, odległość między dwoma stacjami roboczymi w sieci biurowej.
• Szybkość pakietu danych w sieci lub przepustowości.

2. Wykres nieważony

Gdzie nie ma wartości ani wagi związanej z krawędzią. Domyślnie wszystkie wykresy są nieważone, chyba że istnieje powiązana wartość.

3. Wykres nieskierowany

Gdzie zestaw obiektów jest połączony, a wszystkie krawędzie są dwukierunkowe. Poniższy obraz przedstawia wykres nieskierowany,

To jak skojarzenie dwóch użytkowników Facebooka po połączeniu się jako znajomy. Obaj użytkownicy mogą polecać i udostępniać zdjęcia, komentować między sobą.

4. Wyreżyserowany wykres

Nazywany również digrafem, w którym zestaw obiektów (N, E) jest połączony, a wszystkie krawędzie są skierowane z jednego węzła do drugiego. Powyższy obraz przedstawia skierowany wykres.

Zamówienie: projekty wizualizacji danych, które można replikować

Przechowywanie wykresu

Każda metoda przechowywania ma swoje wady i zalety, a odpowiednia metoda przechowywania jest wybierana w oparciu o złożoność. Dwie najczęściej używane struktury danych do przechowywania wykresów to:

1. Lista sąsiedztwa

Tutaj węzły są przechowywane jako indeks tablicy jednowymiarowej, po której następują krawędzie przechowywane jako lista.

2. Macierz sąsiedztwa

Tutaj węzły są reprezentowane jako indeks dwuwymiarowej tablicy, po których następują krawędzie reprezentowane jako niezerowe wartości sąsiedniej macierzy.

Zarówno wiersze, jak i kolumny prezentują węzły; cała macierz jest wypełniona „0” lub „1”, co oznacza prawdę lub fałsz. Zero oznacza brak ścieżki, a 1 oznacza ścieżkę.

Przechodzenie przez wykres

Graph traversal to metoda używana do wyszukiwania węzłów w grafie. Przechodzenie przez wykres służy do określenia kolejności używanej do rozmieszczenia węzłów. Wyszukuje również krawędzie bez tworzenia pętli, co oznacza, że ​​można przeszukiwać wszystkie węzły i krawędzie bez tworzenia pętli.

Istnieją dwie struktury przechodzenia przez graf.

1. DFS (Depth First Search): metoda wyszukiwania dogłębnego

Wyszukiwanie DFS rozpoczyna się od pierwszego węzła i idzie coraz głębiej, eksplorując w dół, aż do znalezienia docelowego węzła. Jeśli klucz docelowy nie zostanie znaleziony, ścieżka wyszukiwania zostanie zmieniona na ścieżkę, która została zatrzymana podczas wyszukiwania początkowego, a ta sama procedura jest powtarzana dla tej gałęzi.

Drzewo opinające jest tworzone na podstawie wyników tego wyszukiwania. Ta metoda drzewa jest bez pętli. Łączna liczba węzłów w strukturze danych stosu jest używana do implementacji przechodzenia DFS.

Kroki, które należy wykonać, aby zaimplementować wyszukiwanie DFS:

Krok 1 – Rozmiar stosu należy zdefiniować w zależności od całkowitej liczby węzłów.

Krok 2 – Wybierz początkowy węzeł dla poprzecznego; należy go umieścić na stosie, odwiedzając ten węzeł.

Krok 3 – Teraz odwiedź sąsiedni węzeł, który nie był wcześniej odwiedzany i wrzuć go do stosu.

Krok 4 – Powtarzaj krok 3, aż nie będzie żadnego sąsiedniego węzła, który nie jest odwiedzany.

Krok 5 – Użyj cofania i jednego węzła, gdy nie ma innych węzłów do odwiedzenia.

Krok 6 – Opróżnij stos, powtarzając kroki 3, 4 i 5.

Krok 7 – Gdy stos jest pusty, ostateczne drzewo spinające jest tworzone poprzez eliminację nieużywanych krawędzi.

Zastosowania DFS to:

• Rozwiązywanie zagadek za pomocą tylko jednego rozwiązania.
• Aby sprawdzić, czy wykres jest dwuczęściowy.
• Sortowanie topologiczne do planowania zadań i wielu innych.

2. BFS (Breadth-First Search): Wyszukiwanie jest realizowane przy użyciu metody kolejkowania

Wyszukiwanie wszerz nawiguje po wykresie w ruchu wszerz i wykorzystuje kolejkę do przeskakiwania z jednego węzła do drugiego po napotkaniu końca ścieżki.

Kroki podjęte w celu wdrożenia wyszukiwania BFS,

Krok 1 – Na podstawie liczby węzłów definiowana jest kolejka.

Krok 2 – Zacznij od dowolnego węzła przemierzania. Odwiedź ten węzeł i dodaj go do kolejki.

Krok 3 – Teraz sprawdź nieodwiedzony węzeł sąsiedni, który znajduje się przed kolejką i dodaj go do kolejki, a nie na początek.

Krok 4 – Teraz zacznij usuwać węzeł, który nie ma żadnych krawędzi do odwiedzenia i nie znajduje się w kolejce.

Krok 5 – Opróżnij kolejkę, powtarzając kroki 4 i 5.

Krok 6 – Usuń nieużywane krawędzie i utwórz drzewo opinające dopiero po opróżnieniu kolejki.

Zastosowania BFS to:

• Sieci Peer to Peer- Podobnie jak w Bittorrent, służy do wyszukiwania wszystkich sąsiednich węzłów.
• Roboty w wyszukiwarce.
• Serwisy społecznościowe i wiele innych.

Rzeczywiste zastosowania wykresu w strukturze danych

Wykresy są wykorzystywane w wielu codziennych zastosowaniach, takich jak reprezentacja sieci (drogi, mapowanie światłowodów, projektowanie płytek drukowanych itp.). Np. W sieci danych Facebook węzły reprezentują użytkownika, jego zdjęcie lub komentarz, a krawędzie reprezentują zdjęcia, komentarze do zdjęcia.

Wykres w strukturze danych ma szerokie zastosowania. Niektóre z godnych uwagi to:

• Interfejsy API wykresów społecznościowych — jest to główny sposób przekazywania danych do iz platformy mediów społecznościowych Facebooka. Jest to interfejs API oparty na protokole HTTP, który służy do programowego wyszukiwania danych, przesyłania zdjęć i filmów, tworzenia nowych historii i wielu innych zadań. Składa się z węzłów, krawędzi i pól; do zapytania używane są określone węzły obiektów. Krawędzie dla grupy obiektów poddawanych jednemu obiektowi i pola są używane do pobierania danych o każdym obiekcie w grupie.
• GraphQL API firmy Yelp — Jest to silnik rekomendacji używany do pobierania określonych danych z platformy Yelp. Tutaj rozkazy służą do znajdowania krawędzi, po czym odpytywany jest określony węzeł, aby uzyskać dokładny wynik. Przyspiesza to proces pobierania.

Na platformie Yelp węzły reprezentują firmę, zawierając identyfikator, nazwę, is_closed i wiele innych właściwości wykresu.

• Algorytmy Optymalizacji Ścieżki — są stosowane w celu znalezienia najlepszego połączenia, które spełnia kryteria prędkości, bezpieczeństwa, paliwa itp. W tym algorytmie jest używany BFS. Najlepszym przykładem jest Google Maps Platform (Maps, Routes APIs).
• Sieci lotów — w sieciach lotów jest to używane do znalezienia zoptymalizowanej ścieżki, która pasuje do struktury danych wykresu . Pomaga to również w modelu i skutecznie optymalizuje procedury lotniskowe.

Przeczytaj także: Korzyści z wizualizacji danych

Wniosek

W tym artykule najpierw omówiliśmy definicję wykresu i wykresu w strukturze danych, a następnie poznaliśmy rodzaje wykresów wraz z ich właściwościami. Później dowiedzieliśmy się o powszechnie stosowanych metodach przechowywania wykresów, a następnie o ważnych metodach wyszukiwania tematów stosowanych w Graphs, Graph Traversal. Na koniec omówiliśmy rzeczywiste zastosowania grafowej struktury danych.

Artykuł ten dostarczył informacji na temat wykresów w strukturze danych ; wiedza na ten temat jest niezbędna do podstawowego zrozumienia baz danych Graph, implementacji algorytmów wyszukiwania, programowania i wielu innych. Trzeba się tego nauczyć od branżowego eksperta.

Dlaczego warto wybrać kurs z upGrad ?

Zalecamy wybranie programu Executive PG in Data Science oferowanego przez IIIT Bangalore hostowanego na upGrad, ponieważ tutaj możesz uzyskać swoje pytania 1-1 z instruktorami kursu. Koncentruje się nie tylko na nauce teoretycznej, ale przywiązuje wagę do wiedzy praktycznej, która jest niezbędna, aby przygotować uczniów do stawienia czoła projektom w świecie rzeczywistym i zapewnić pierwszy indyjski certyfikat NASSCOM, który pomaga w zdobyciu dobrze płatnej pracy w Data Science.

Prace cytowane

Wydział Matematyki/CS – Strona główna , www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html.

„Wgląd matematyczny”. Definicja wykresu ukierunkowanego — Math Insight , mathinsight.org/definition/directed_graph.

Singh, Amritpal. „Struktura danych wykresu”. Średni , Średni, 29 marca 2020 r., medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3.

Solo. „Prawdziwe zastosowania grafowych struktur danych, które musisz znać”. Graph Data i GraphQL API Development-Leap Graph , leapgraph.com/graph-data-structures-applications.