Разлика између стабла и графа
Садржај
Дрво и граф спадају у категорију нелинеарне структуре података где дрво нуди врло користан начин представљања односа између чворова у хијерархијској структури, а граф следи мрежни модел. Дрво и граф разликују се чињеницом да структура стабла мора бити повезана и никад не може имати петље док у графикону нема таквих ограничења.
Нелинеарна структура података састоји се од скупа елемената који су распоређени на равнини, што значи да не постоји такав низ између елемената као што постоји у линеарној структури података.
-
- Упоредни графикон
- Дефиниција
- Кључне разлике
- Закључак
Упоредни графикон
| Основе за поређење | Дрво | Графикон |
|---|---|---|
| Стаза | Само једна између две врхове. | Више од једне стазе је дозвољено. |
| Роот чвор | Има тачно један коријенски чвор. | Граф нема коријенски чвор. |
| Петље | Није допуштена петља. | Графикон може имати петље. |
| Сложеност | Мање сложен | Сложеније компаративно |
| Технике преласка | Предбиљежба, наруџба и Предбиљежба. | Прво претраживање ширине и прво претраживање дубине. |
| Број ивица | н-1 (где је н број чворова) | Није дефинисано |
| Тип модела | Хијерархијски | Мрежа |
Дефиниција стабла
А дрво је ограничена збирка података који се обично називају чворови. Као што је горе поменуто, стабло је нелинеарна структура података која распоређује ставке података у пореданим редоследом. Користи се за приказивање хијерархијске структуре између различитих елемената података и организује податке у гране које односе информације. Додавање нове ивице у дрво резултира формирањем петље или круга.
Постоји неколико врста дрвећа као што су бинарно стабло, бинарно стабло претраживања, АВЛ стабло, бинарно стабло са навојем, Б стабло итд. Компресија података, складиштење датотека, манипулација аритметичким изразом и дрвеће игара су неке од примена стабла структура података.
Својства дрвета:
- На врху стабла је означен чвор познат као корен дрвета.
- Преостале ставке података подијељене су у одвојене подскупове који се називају поддрева.
- Дрво је у висини проширено према дну.
- Дрво мора бити повезано што значи да мора постојати пут од једног коријена до свих осталих чворова.
- Не садржи петље.
- Дрво има н-1 ивице.
Постоје различити изрази повезани са дрвећем као што су терминални чвор, ивица, ниво, степен, дубина, шума итд. Међу тим терминима су неки од њих описани у даљем тексту.
- Ивица - Линија која повезује два чвора.
- Ниво - Дрво је подељено на нивое тако да коријенски чвор буде на нивоу 0. Затим су његова непосредна дјеца на нивоу 1, а његова непосредна дјеца на нивоу 2 и тако даље, до терминалног или чворова листа.
- Степен - То је број подврста чворова у датом стаблу.
- Дубина - То је максимални ниво било којег чвора на одређеном стаблу и такође познат као висина.
- Терминални чвор - Чвор највише разине је терминални чвор док су други чворови осим терминалног и коријенског чвора познати као не-терминални чворови.
Дефиниција графикона
А граф је такође математичка нелинеарна структура података која може представљати различите врсте физичке структуре. Састоји се од групе врхова (или чворова) и скупа ивица које повезују две врхове. Врхови на графу представљени су као тачка или кругови, а ивице су приказане као лукови или сегменти линија. Ивица је представљена Е (в, в) где су в и в парови врхова. Уклањање ивице са круга или повезаног графа ствара подграф који је стабло.
Графови су класификовани у различите категорије као што су усмерени, ненамерни, повезани, неповезани, једноставни и вишеструки. Рачунарска мрежа, транспортни систем, граф друштвене мреже, електрични кругови и планирање пројеката су неке од примена структуре података графикона. Такође се користи у техници управљања под називом ПЕРТ (техника евалуације и прегледа програма) и ЦПМ (метода критичног пута) у којој се анализира структура графа.
Својства графа:
- Врхови у графикону могу бити повезани са било којим бројем других врхова помоћу ивица.
- Ивица може бити двосмерна или усмерена.
- Ивица се може извагати.
У графикону такође користимо разне изразе као што су суседни врхови, путања, циклус, степен, повезани графикон, комплетан граф, пондерисани граф итд. Разумејмо неке од ових термина.
- Суссед вертицес - Врхова а је уз врх б ако постоји ивица (а, б) или (б, а).
- Стаза - Пут од насумичне вршне точке в је суседни низ вертикала.
- Циклус - То је стаза на којој су прва и последња врхова исте.
- Степен - То је већи број ивица које се јављају на једном врхунцу.
- Повезани граф - Ако постоји пут од случајне вршце до било које друге вертека, тада је тај граф познат као повезан графикон.
- У стаблу постоји само једна стаза између било које две врхове док граф може имати једносмерне и двосмерне стазе између чворова.
- У дрвету се налази тачно један коријенски чвор и свако дијете може имати само једног родитеља. Насупрот томе, у графикону не постоји концепт коренског чвора.
- Дрво не може имати петље и самообликовања, док граф може имати петље и самољупце.
- Графикони су сложенији јер могу имати петље и саморезне петље. Насупрот томе, дрвеће је у поређењу са графиконом једноставно.
- Стабло се прелази помоћу техника предбиљежбе, наруџбе и накнадне наруџбе. Са друге стране, за помицање графикона користимо БФС (прва ширина претраживања) и ДФС (Дубина прва претрага).
- Дрво може имати н-1 ивице. Напротив, у графикону нема унапред дефинисаног броја ивица, а зависи и од графа.
- Дрво има хијерархијску структуру док граф има мрежни модел.
Закључак
Граф и стабло су нелинеарна структура података која се користи за решавање различитих сложених проблема. Граф је група врхова и ивица где ивица повезује пар врхова док се дрво сматра минимално повезаним графом који мора бити повезан и без петљи.
