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