Jaka jest różnica między drzewem struktury danych a wykresem?

Z naukowego punktu widzenia, jaka jest zasadnicza różnica między drzewem struktury danych a wykresem? A co z wyszukiwaniem opartym na drzewie i na wykresie?

Drzewo to tylko ograniczona forma wykresu.

Drzewa mają kierunek (relacje rodzic / potomek) i nie zawierają cykli. Pasują do kategorii Skierowanych Grafów Acyklicznych (lub DAG). Drzewa są więc DAG-ami z zastrzeżeniem, że dziecko może mieć tylko jednego rodzica.

Jedna rzecz, na którą należy zwrócić uwagę, drzewa nie są cykliczną strukturą danych. Nie można ich zaimplementować jako rekursywnej struktury danych z powodu powyższych ograniczeń. Ale można również użyć dowolnej implementacji DAG, która na ogół nie jest rekurencyjna. Moja preferowana implementacja drzewa to scentralizowana reprezentacja mapy i nie jest rekurencyjna.

Wykresy są zazwyczaj przeszukiwane najpierw wszerz lub najpierw w głąb. To samo dotyczy Tree.

Zamiast wyjaśniać, wolę pokazać to na zdjęciach.

Drzewo w czasie rzeczywistym

Wykres w prawdziwym życiu

Tak, mapę można wizualizować jako graficzną strukturę danych.

Zobaczenie ich w ten sposób ułatwia życie. Drzewa są używane w miejscach, w których wiemy, że każdy węzeł ma tylko jednego rodzica. Jednak wykresy mogą mieć wielu poprzedników (termin rodzic na ogół nie jest używany w przypadku wykresów).

W prawdziwym świecie możesz przedstawić prawie wszystko za pomocą wykresów. Na przykład użyłem mapy. Jeśli uznasz każde miasto za węzeł, można do niego dotrzeć z wielu punktów. Punkty prowadzące do tego węzła nazywane są poprzednikami, a punkty, do których ten węzeł prowadzi, nazywane są następcami.

schemat obwodu elektrycznego, plan domu, sieć komputerowa czy system rzeczny to jeszcze kilka przykładów wykresów. Wiele przykładów ze świata rzeczywistego można uznać za wykresy.

Schemat techniczny mógłby wyglądać tak

Drzewo:

Wykres:

Pamiętaj, aby zapoznać się z poniższymi linkami. Będą one odpowiedzią na prawie wszystkie pytania dotyczące drzew i wykresów.

Bibliografia :

1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

3. Wikipedia

Pozostałe odpowiedzi są przydatne, ale brakuje im właściwości każdej z nich:

Wykres

^{Niekierunkowy wykres, źródło obrazu: Wikipedia}

^{Wykres skierowany, źródło zdjęcia: Wikipedia}

• Składa się z zestawu wierzchołków (lub węzłów) i zestawu krawędzi łączących niektóre lub wszystkie z nich
• Dowolna krawędź może łączyć dowolne dwa wierzchołki, które nie są jeszcze połączone identyczną krawędzią (w tym samym kierunku, w przypadku wykresu skierowanego)
• Nie musi być łączony (krawędzie nie muszą łączyć wszystkich wierzchołków razem): pojedynczy wykres może składać się z kilku rozłącznych zestawów wierzchołków

• Może być skierowany lub nieukierunkowany (co dotyczy wszystkich krawędzi na wykresie)
  Zgodnie z Wikipedią :

  Na przykład, jeśli wierzchołki przedstawiają ludzi na przyjęciu, a między dwiema osobami jest krawędź, jeśli podają sobie ręce, to ten wykres jest nieukierunkowany, ponieważ każda osoba A może uścisnąć dłoń osobie B tylko wtedy, gdy B również podaje rękę z A. W przeciwieństwie do tego, jeśli jakakolwiek krawędź od osoby A do osoby B odpowiada A podziwiającemu B, to ten wykres jest skierowany, ponieważ podziw niekoniecznie jest odwzajemniony.

Drzewo

^{Źródło obrazu: Wikipedia}

• Rodzaj wykresu
• Wierzchołki są częściej nazywane „węzłami”
• Krawędzie są skierowane i reprezentują relację „jest dzieckiem” (lub „jest rodzicem”)
• Każdy węzeł (z wyjątkiem węzła głównego) ma dokładnie jednego rodzica (i zero lub więcej dzieci)
• Ma dokładnie jeden węzeł „główny” (jeśli drzewo ma przynajmniej jeden węzeł), który jest węzłem bez rodzica
• Musi być podłączony
• Jest acykliczny, co oznacza, że ​​nie ma cykli : „cykl jest ścieżką [sekwencją AKA] krawędzi i wierzchołków, w których wierzchołek jest osiągalny od samego siebie”

Powyższe właściwości w pewnym stopniu pokrywają się. W szczególności dwie ostatnie właściwości są implikowane przez pozostałe właściwości. Niemniej jednak wszystkie z nich są warte odnotowania.

W drzewie każdy węzeł (z wyjątkiem węzła głównego) ma dokładnie jeden poprzedni węzeł i jeden lub dwa kolejne węzły. Można przez nią przejść, korzystając z przejść w kolejności, w przedsprzedaży, na zamówienie i wszerz. Drzewo to specjalny rodzaj wykresu, który nie ma cyklu, więc jest znany jako DAG (Directed Acyclic Graph). Drzewo to model hierarchiczny.

Na wykresie każdy węzeł ma jeden lub więcej węzłów poprzedzających i następnych. Wykres jest przemierzany przy użyciu algorytmów wyszukiwania według głębokości (DFS) i przeszukiwania szerokości (BFS). Wykres ma cykl, więc jest bardziej złożony niż drzewo. Graph to model sieciowy. Istnieją dwa rodzaje wykresów: wykresy skierowane i wykresy nieukierunkowane.

Drzewa są oczywiste: to rekurencyjne struktury danych składające się z węzłów z dziećmi.

Mapa (inaczej słownik) to pary klucz / wartość. Daj mapie klucz, a zwróci ona powiązaną wartość.

Mapy można zaimplementować za pomocą drzew, mam nadzieję, że nie będzie to dla ciebie mylące.

AKTUALIZACJA: Mylenie „wykresu” z „mapą” jest bardzo mylące.

Wykresy są bardziej złożone niż drzewa. Drzewa implikują rekurencyjne relacje rodzic / dziecko. Istnieją naturalne sposoby przemieszczania się po drzewie: najpierw w głąb, wszerz wszerz, w kolejności poziomów itp.

Grafy mogą mieć jednokierunkowe lub dwukierunkowe ścieżki między węzłami, być cykliczne lub acykliczne itp. Uważam, że wykresy są bardziej złożone.

Myślę, że pobieżne przeszukiwanie dowolnego porządnego tekstu struktury danych (np. „Podręcznik projektowania algorytmów”) dałoby więcej i lepszych informacji niż jakakolwiek liczba odpowiedzi SO. Zalecałbym, abyś nie wybierał ścieżki pasywnej i zaczął samodzielnie szukać informacji.

Drzewo jest specjalną formą grafu, tj. Grafem minimalnie połączonym i posiadającym tylko jedną ścieżkę pomiędzy dowolnymi dwoma wierzchołkami.

Na grafie może być więcej niż jedna ścieżka, tj. Graf może mieć jednokierunkowe lub dwukierunkowe ścieżki (krawędzie) między węzłami

Możesz również zobaczyć więcej szczegółów: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

W matematyce wykres jest reprezentacją zbioru obiektów, w których niektóre pary obiektów są połączone linkami. Połączone obiekty są reprezentowane przez matematyczne abstrakcje zwane wierzchołkami, a łącza, które łączą niektóre pary wierzchołków, nazywane są krawędziami. [1] Zazwyczaj wykres jest przedstawiany w formie diagramu jako zbiór punktów na wierzchołkach, połączonych liniami lub krzywymi dla krawędzi. Grafy są jednym z przedmiotów badań matematyki dyskretnej.

jeden węzeł główny w drzewie i tylko jeden rodzic dla jednego dziecka. Jednak nie ma koncepcji węzła głównego. Inną różnicą jest to, że drzewo to model hierarchiczny, a wykres to model sieci.

Drzewo jest dwuznakiem takim, że:

a) z usuniętymi kierunkami krawędzi jest połączony i acykliczny

1. Możesz usunąć albo założenie, że jest acykliczny
2. Jeśli jest skończony, możesz alternatywnie usunąć założenie, że jest połączony

b) każdy wierzchołek oprócz jednego, korzenia, ma nie stopień 1

c) korzeń ma niezależne 0

1. Jeśli jest tylko skończona liczba węzłów, możesz usunąć założenie, że korzeń ma nieegree 0 lub założenie, że węzły inne niż korzeń mają stopień 1

Źródła: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

Drzewo jest w zasadzie wykresem bezkierunkowym, który nie zawiera cykli, więc można powiedzieć, że drzewo jest bardziej ograniczoną formą wykresu. Jednak drzewo i wykres mają różne zastosowania do implementacji różnych algorytmów w programowaniu. Na przykład wykres może służyć do modelowania mapy drogowej, a drzewo do implementacji dowolnej hierarchicznej struktury danych.