Wprowadzenie do wykresu w strukturze danych

Wykresy to nieliniowe struktury danych zawierające skończony zestaw węzłów i krawędzi. Węzły są elementami, a krawędzie są uporządkowane parami połączeń między węzłami.

Zwróć uwagę na słowo nieliniowe. Nieliniowa struktura danych to taka, w której elementy nie są ułożone w kolejności sekwencyjnej. Na przykład tablica jest liniową strukturą danych, ponieważ elementy są ułożone jeden po drugim. Możesz przeglądać wszystkie elementy tablicy w jednym przebiegu. Tak nie jest w przypadku nieliniowych struktur danych. Elementy nieliniowej struktury danych są rozmieszczone na wielu poziomach, często według hierarchicznego wzorca. Wykresy są nieliniowe.

Następne słowo, na które należy zwrócić uwagę, jest skończone. Definiujemy wykres, aby miał skończoną i policzalną liczbę węzłów. Jest to raczej niezgodny termin. Zasadniczo wykres może mieć nieskończoną liczbę węzłów i nadal być skończony. Na przykład drzewo genealogiczne od Adama i Ewy. Jest to wykres względnie nieskończony, ale nadal można go policzyć i dlatego jest uważany za skończony.

Przykład ze świata rzeczywistego

Najlepszym przykładem wykresów w prawdziwym świecie jest Facebook. Każda osoba na Facebooku jest węzłem i jest połączona za pomocą krawędzi. A jest przyjacielem B. B jest przyjacielem C i tak dalej.

Terminologie

Oto wspomniane poniżej terminologie wykresu w strukturze danych

1. Reprezentacja wykresu: Ogólnie wykres jest reprezentowany jako para zestawów (V, E). V jest zbiorem wierzchołków lub węzłów. E jest zbiorem krawędzi. W powyższym przykładzie
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)

2. Węzeł lub wierzchołek: elementy wykresu są połączone krawędziami.

3. Krawędzie: ścieżka lub linia między dwoma wierzchołkami na wykresie.

4. Sąsiadujące węzły: Dwa węzły są nazywane sąsiadującymi, jeśli są połączone przez krawędź. W powyższym przykładzie węzeł A sąsiaduje z węzłami B, C i D, ale nie z węzłem E.

5. Ścieżka: Ścieżka jest sekwencją krawędzi między dwoma węzłami. Zasadniczo jest to przejście od jednego węzła do drugiego. W powyższym przykładzie istnieje wiele ścieżek od węzła A do węzła E.

Ścieżka (A, E) = (AB, BE)
LUB
Ścieżka (A, E) = (AC, CD, DE)
LUB
Ścieżka (A, E) = (AD, DE)

6. Niekierowany wykres: Niekierowany wykres to taki, w którym krawędzie nie określają określonego kierunku. Krawędzie są dwukierunkowe.

Przykład

Zatem w tym przykładzie krawędź AC może być przemieszczana zarówno od A do C, jak i od C do A. Podobnie do wszystkich krawędzi. Ścieżka od węzła B do węzła C miałaby postać (BA, AC) lub (BD, DC).

7. Wykres kierunkowy: Wykres kierunkowy to taki, w którym krawędzie można przemieszczać tylko w określonym kierunku.

Przykład

Zatem w tym samym przykładzie teraz krawędzie są kierunkowe. Możesz tylko przesuwać krawędź wzdłuż jej kierunku. Nie ma teraz ścieżki od węzła B do węzła C.

8. Wykres ważony: wykres ważony to taki, w którym krawędzie są powiązane z wagą. Jest to ogólnie koszt przejścia przez krawędź.

Przykład

Zatem w tym samym przykładzie teraz krawędzie mają pewną wagę. Istnieją dwie możliwe ścieżki między węzłem A a węzłem E.
Ścieżka 1 = (AB, BD, DE), waga 1 = 3 + 2 + 5 = 10
Ścieżka 2 = (AC, CD, DE), Waga 2 = 1 + 3 + 5 = 9
Oczywiście wolelibyśmy Ścieżkę 2, jeśli celem jest dotarcie do węzła E z węzła A przy minimalnym koszcie.

Podstawowe operacje na wykresie

Oto podstawowe operacje na wykresie wymienione poniżej

1. Dodaj / Usuń wierzchołek

Jest to najprostsza operacja na wykresie. Po prostu dodajesz wierzchołek do wykresu. Nie musi być połączony z żadnym innym wierzchołkiem przez krawędź. Podczas usuwania wierzchołka należy usunąć wszystkie krawędzie rozpoczynające się i kończące na usuniętym wierzchołku.

2. Dodaj / Usuń krawędź

Ta operacja dodaje lub usuwa krawędź między dwoma wierzchołkami. Po usunięciu wszystkich krawędzi rozpoczynających się i kończących się wierzchołkiem wierzchołek staje się wierzchołkiem izolowanym.

3. Szerokie wyszukiwanie pierwsze (BFS)

Jest to operacja przejścia na wykresie. BFS poziomo przechodzi przez wykres. Oznacza to, że przechodzi przez wszystkie węzły na jednym poziomie, zanim przejdzie do następnego poziomu.
Algorytm BFS rozpoczyna się u góry pierwszego węzła na wykresie, a następnie przechodzi do niego przez wszystkie sąsiednie węzły. Po przejściu wszystkich sąsiednich węzłów algorytm powtarza tę samą procedurę dla węzłów potomnych.

Przykład

Przejście powyższego wykresu w stylu BFS wynikałoby z A -> B -> C -> D -> E -> F -> G. Algorytm rozpoczyna się od węzła A i przechodzi przez wszystkie sąsiednie węzły B, C i D. wszystkie cztery węzły, które odwiedzono. Po przejściu wszystkich sąsiednich węzłów A algorytm przenosi się do pierwszego sąsiedniego węzła A i powtarza tę samą procedurę. W tym przypadku węzłem jest B, a sąsiednie węzły B to E i F. Następnie sąsiednie węzły C przechodzą. Po odwiedzeniu wszystkich węzłów operacja kończy się.

4. Głębokie pierwsze wyszukiwanie (DFS)

Głębokie pierwsze wyszukiwanie lub DFS przegląda wykres w pionie. Zaczyna się od węzła głównego lub pierwszego węzła wykresu i przechodzi przez wszystkie węzły potomne przed przejściem do sąsiednich węzłów.

Przykład

Przemieszczanie powyższego wykresu w stylu BFS wynikałoby z A -> B -> E -> F -> C -> G -> D. Algorytm rozpoczyna się od węzła A i przechodzi przez wszystkie jego węzły potomne. Gdy tylko napotka B, wydaje się, że ma kolejne węzły potomne. Tak więc węzły potomne B przechodzą przez przejście przed przejściem do następnego węzła potomnego A.

Realne wykresy w świecie rzeczywistym

  • Projektowanie obwodów elektrycznych do przesyłania energii.
  • Projektowanie sieci połączonych komputerów.
  • Badanie struktury molekularnej, chemicznej i komórkowej dowolnej substancji, np. Ludzkiego DNA.
  • Projektowanie tras transportowych między miastami i miejscami w obrębie miasta.

Wniosek - wykres w strukturze danych

Wykresy są bardzo przydatną koncepcją w strukturach danych. Ma praktyczne zastosowania w prawie każdej dziedzinie. Bardzo ważne jest zrozumienie podstaw teorii grafów, aby rozwinąć zrozumienie algorytmów struktury grafu.
Ten artykuł był jedynie wstępem do wykresów. To tylko odskocznia. Zaleca się głębsze zanurzenie w temacie teorii grafów.

Polecane artykuły

Jest to przewodnik po wykresie w strukturze danych. Tutaj omawiamy terminologie i podstawowe operacje wykresu w strukturze danych. Możesz także spojrzeć na następujący artykuł, aby dowiedzieć się więcej -

  1. Pytania do wywiadu dotyczącego struktury danych
  2. Model danych w Cassandrze
  3. Co to jest Data Mart?
  4. Co to jest Data Scientist?

Kategoria:

Big Data