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?
Jaka jest różnica między drzewem struktury danych a wykresem?
Odpowiedzi:
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.
8
Wykresy są bardzo przydatne i można ich używać do modelowania ogromnej liczby rzeczy. Wiele innych struktur danych można postrzegać jako wykres z ograniczeniami. Na przykład lista pojedynczo połączona jest specjalnym przypadkiem DAG.
—
JR Garcia
@ user785287 co masz na myśli mówiąc o scentralizowanej reprezentacji mapy ?
—
Geek
„Drzewa nie są rekursywną strukturą danych” jest mylące i błędne. Drzewo można przedstawić za pomocą nierekurencyjnej struktury danych (np. Tablica krawędzi; pełne drzewo, takie jak to leżące u podstaw stosu binarnego, może być reprezentowane bardzo zwięźle w tablicy; istnieją inne zwięzłe reprezentacje itp.), ale prawdopodobnie najbardziej popularnym i użytecznym sposobem ich przedstawienia jest rekurencyjna struktura oparta na wskaźnikach. Przedstawienie nie jest unikalne dla drzew nieukorzenionych, ale nie ma to znaczenia.
—
j_random_hacker,
Nie do końca. Drzewo niekoniecznie ma kierunek. en.wikipedia.org/wiki/Tree_(graph_theory) przedstawia przykład drzewa bez kierunku. Są one często używane w kontekstach biologicznych.
—
Michał Palczewski
Drzewa @ harshpatel991 nie są kierowane w tym sensie, że „X i Y są w relacji rodzic-dziecko” nie mają kierunku. Jednak relacje indywidualne, „X jest dzieckiem Y” i „Y jest dzieckiem X”, są relacjami ukierunkowanymi. Kierunek właśnie na to wskazuje; kierunek „ruchu”. W przypadku drzew idea kierunku nie jest tak naprawdę potrzebna, chyba że ma znaczenie (co jest najczęściej w przypadku drzew). Przynajmniej tak to postrzegam.
—
Kostas Mouratidis
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 :
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
- 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.
Przepraszam, mam na myśli wykres, wpisałem mapę.
—
user918304
„Mylący” wykres dla „mapy” jest bardzo mylący ”. :)
—
cpz
Powiedzenie „wykresy są bardziej złożone niż drzewa” jest jak powiedzenie „Wrony są bardziej wyspecjalizowane niż ptaki”. Czy nie powinniśmy zamiast tego powiedzieć, że „Wszystkie drzewa są wykresami, ale nie wszystkie wykresy są drzewami”?
—
dudewad
Nie obchodzi mnie to sześć lat później. Z pewnością możesz lepiej wykorzystać tutaj swój czas.
—
duffymo
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
- Możesz usunąć albo założenie, że jest acykliczny
- 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
- 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.