Różnica między drzewem a wykresem
Zawartość
Drzewo i wykres należą do kategorii nieliniowej struktury danych, w której drzewo oferuje bardzo użyteczny sposób przedstawienia relacji między węzłami w strukturze hierarchicznej, a wykres oparty jest na modelu sieci. Drzewo i wykres różnią się tym, że struktura drzewa musi być połączona i nigdy nie może mieć pętli, podczas gdy na wykresie nie ma takich ograniczeń.
Nieliniowa struktura danych składa się ze zbioru elementów rozmieszczonych na płaszczyźnie, co oznacza, że nie ma takiej sekwencji między elementami, jaka istnieje w liniowej strukturze danych.
-
- Wykres porównania
- Definicja
- Kluczowe różnice
- Wniosek
Wykres porównania
| Podstawa do porównania | Drzewo | Wykres |
|---|---|---|
| Ścieżka | Tylko jeden między dwoma wierzchołkami. | Dozwolona jest więcej niż jedna ścieżka. |
| Węzeł główny | Ma dokładnie jeden węzeł główny. | Wykres nie ma węzła głównego. |
| Pętle | Pętle nie są dozwolone. | Wykres może mieć pętle. |
| Złożoność | Mniej skomplikowane | Porównywalnie bardziej złożony |
| Techniki przejścia | Zamów w przedsprzedaży, zamów w przedsprzedaży i zamów w przedsprzedaży. | Wyszukiwanie w pierwszej kolejności i wyszukiwanie w pierwszej kolejności. |
| Liczba krawędzi | n-1 (gdzie n jest liczbą węzłów) | Nie zdefiniowano |
| Typ modelu | Hierarchiczny | Sieć |
Definicja drzewa
ZA drzewo to skończony zbiór elementów danych zwykle określanych jako węzły. Jak wspomniano powyżej, drzewo jest nieliniową strukturą danych, która porządkuje elementy danych w posortowanej kolejności. Służy do pokazania hierarchicznej struktury między różnymi elementami danych i organizuje dane w gałęzie, które odnoszą się do informacji. Dodanie nowej krawędzi do drzewa powoduje utworzenie pętli lub obwodu.
Istnieje kilka rodzajów drzew, takich jak drzewo binarne, drzewo wyszukiwania binarnego, drzewo AVL, wątkowe drzewo binarne, drzewo B itp. Kompresja danych, przechowywanie plików, manipulowanie wyrażeniem arytmetycznym i drzewa gry to tylko niektóre z zastosowań drzewa struktura danych.
Właściwości drzewa:
- Na górze drzewa znajduje się wyznaczony węzeł, zwany korzeniem drzewa.
- Pozostałe elementy danych są podzielone na rozłączne podzbiory nazywane poddrzewami.
- Drzewo rozszerza się w kierunku dołu.
- Drzewo musi być połączone, co oznacza, że musi istnieć ścieżka z jednego katalogu głównego do wszystkich innych węzłów.
- Nie zawiera żadnych pętli.
- Drzewo ma krawędzie n-1.
Istnieją różne terminy związane z drzewami, takie jak węzeł końcowy, krawędź, poziom, stopień, głębokość, las itp. Wśród tych terminów niektóre z nich opisano poniżej.
- Brzeg - Linia łącząca dwa węzły.
- Poziom - Drzewo jest podzielone na poziomy w taki sposób, że węzeł główny znajduje się na poziomie 0. Następnie jego bezpośrednie elementy potomne znajdują się na poziomie 1, a jego bezpośrednie elementy potomne są na poziomie 2 i tak dalej, aż do węzła końcowego lub liścia.
- Stopień - Jest to liczba poddrzewa węzła w danym drzewie.
- Głębokość - Jest to maksymalny poziom dowolnego węzła w danym drzewie, znany również jako wysokość.
- Węzeł końcowy - Węzłem najwyższego poziomu jest węzeł końcowy, podczas gdy inne węzły z wyjątkiem węzła końcowego i głównego są znane jako węzły nieterminalne.
Definicja wykresu
ZA wykres jest również matematyczną nieliniową strukturą danych, która może reprezentować różne rodzaje struktury fizycznej. Składa się z grupy wierzchołków (lub węzłów) i zestawu krawędzi łączących dwa wierzchołki. Wierzchołki na wykresie są reprezentowane jako punkt lub koła, a krawędzie są pokazane jako łuki lub segmenty linii. Krawędź jest reprezentowana przez E (v, w), gdzie v i w są parami wierzchołków. Usunięcie krawędzi z obwodu lub podłączonego wykresu tworzy podgraf, który jest drzewem.
Wykresy są podzielone na różne kategorie, takie jak ukierunkowane, niekierowane, połączone, niepołączone, proste i wielogramowe. Sieć komputerowa, system transportu, wykres sieci społecznościowych, obwody elektryczne i planowanie projektu to tylko niektóre z zastosowań struktury danych wykresu. Jest również stosowany w technice zarządzania o nazwie jako ZUCHWAŁY (technika oceny i przeglądu programu) oraz CPM (metoda ścieżki krytycznej), w której analizowana jest struktura wykresu.
Właściwości wykresu:
- Wierzchołek na wykresie można połączyć z dowolną liczbą innych wierzchołków za pomocą krawędzi.
- Krawędź może być dwukierunkowa lub skierowana.
- Krawędź może być ważona.
Na wykresie używamy również różnych terminów, takich jak sąsiednie wierzchołki, ścieżka, cykl, stopień, połączony wykres, pełny wykres, wykres ważony itp. Przyjrzyjmy się niektórym z tych terminów.
- Sąsiadujące wierzchołki - Wierzchołek a przylega do wierzchołka b, jeżeli istnieje krawędź (a, b) lub (b, a).
- Ścieżka - Ścieżka od losowego wierzchołka w jest sąsiednią sekwencją wierzchołków.
- Cykl - Jest to ścieżka, na której pierwszy i ostatni wierzchołek są takie same.
- Stopień - Jest to liczba krawędzi padających na wierzchołek.
- Połączony wykres - Jeśli istnieje ścieżka od wierzchołka losowego do dowolnego innego wierzchołka, wówczas ten wykres jest znany jako wykres połączony.
- W drzewie istnieje tylko jedna ścieżka między dowolnymi dwoma wierzchołkami, podczas gdy wykres może mieć jednokierunkowe i dwukierunkowe ścieżki między węzłami.
- W drzewie jest dokładnie jeden węzeł główny, a każde dziecko może mieć tylko jednego rodzica. Przeciwnie, na wykresie nie ma koncepcji węzła głównego.
- Drzewo nie może mieć pętli i pętli własnych, a wykres może zawierać pętle i pętle własne.
- Wykresy są bardziej skomplikowane, ponieważ mogą zawierać pętle i pętle własne. Natomiast drzewa są proste w porównaniu do wykresu.
- Drzewo jest trawersowane przy użyciu technik zamówień w przedsprzedaży, zamówień w kolejności i zamówień. Z drugiej strony, do przechodzenia przez wykres używamy BFS (pierwsze wyszukiwanie szerokości) i DFS (pierwsze wyszukiwanie głębokości).
- Drzewo może mieć krawędzie n-1. Przeciwnie, na wykresie nie ma z góry określonej liczby krawędzi i zależy to od wykresu.
- Drzewo ma strukturę hierarchiczną, podczas gdy wykres ma model sieci.
Wniosek
Wykres i drzewo to nieliniowa struktura danych, która służy do rozwiązywania różnych złożonych problemów. Wykres to grupa wierzchołków i krawędzi, w których krawędź łączy parę wierzchołków, podczas gdy drzewo jest uważane za wykres minimalnie połączony, który musi być połączony i wolny od pętli.
