Nelinijinė duomenų struktūra susideda iš elementų, paskirstytų plokštumoje, tai reiškia, kad tarp elementų nėra tokios sekos, kaip ji yra linijinėje duomenų struktūroje.
Palyginimo diagrama
| Palyginimo pagrindas | Medis | Grafikas |
|---|---|---|
| Kelias | Tik viena iš dviejų viršūnių. | Leidžiama naudoti daugiau nei vieną kelią. |
| Šaknų mazgas | Jame yra vienas šakninis mazgas. | Grafike nėra šaknų mazgo. |
| Kilpos | Neleidžiama naudoti jokių kilpų. | Grafikas gali turėti kilpas. |
| Sudėtingumas | Mažiau sudėtingas | Palyginti sudėtingiau |
| Traverso metodai | Išankstinis užsakymas, užsakymas ir užsakymas. | Pirmoji paieška ir pirmoji paieška. |
| Briaunų skaičius | n-1 (kur n yra mazgų skaičius) | Neapibrėžtas |
| Modelio tipas | Hierarchinis | Tinklas |
Medžio apibrėžimas
Medis yra baigtinis duomenų elementų rinkinys, paprastai vadinamas mazgais. Kaip jau minėta, medis yra nelinijinė duomenų struktūra, kuri tvarko duomenų elementus rūšiuojama tvarka. Jis naudojamas rodyti įvairių duomenų elementų hierarchinę struktūrą ir tvarko duomenis į filialus, kurie sieja informaciją. Pridėjus naują kraštą medyje susidaro kilpa ar grandinė.
Yra keletas medžių rūšių, pvz., Dvejetainis medis, dvejetainis paieškos medis, AVL medis, srieginis dvejetainis medis, B-medis ir tt Duomenų suspaudimas, failų saugojimas, aritmetinės išraiškos manipuliavimas ir žaidimo medžiai yra dalis medžio taikymo duomenų struktūra.
Medžio savybės:
- Medžio viršuje yra vadinamas mazgas, vadinamas medžio šaknimi.
- Likusieji duomenų elementai yra suskirstyti į atskirus pogrupius, nurodytus kaip subtree.
- Medis yra išplečiamas į apačią.
- Medis turi būti sujungtas, o tai reiškia, kad turi būti kelias iš vienos šaknies į visus kitus mazgus.
- Jame nėra kilpų.
- Medis turi n-1 kraštus.
Yra įvairių su medžių susijusių terminų, pvz., Terminalo mazgas, kraštas, lygis, laipsnis, gylis, miškas ir tt Tarp šių terminų, kai kurie iš jų aprašyti žemiau.
- Briauna - linija, jungianti du mazgus.
- Lygis - medis yra suskirstytas į lygius taip, kad šakninis mazgas būtų 0 lygiu. Tada jo artimiausi vaikai yra 1 lygyje, o jo tiesioginiai vaikai yra 2 lygiu ir pan. Iki terminalo ar lapų mazgo.
- Laipsnis - tai tam tikro medžio mazgo mazgų skaičius.
- Gylis - tai maksimalus bet kurio mazgo lygis konkrečiame medyje ir taip pat žinomas kaip aukštis .
- Terminalo mazgas - aukščiausio lygio mazgas yra galinis mazgas, o kiti mazgai, išskyrus terminalą ir šaknų mazgus, yra žinomi kaip ne terminaliniai mazgai.
Grafiko apibrėžimas
Grafikas taip pat yra matematinė nelinijinė duomenų struktūra, kuri gali atstovauti įvairių rūšių fizinei struktūrai. Jį sudaro viršūnių (arba mazgų) ir briaunų, jungiančių dvi viršūnes, grupė. Grafų vertikalės yra pateikiamos kaip taškas arba apskritimai ir briaunos yra rodomi kaip lankai arba linijos segmentai. Briauna yra E (v, w), kur v ir w yra viršūnių poros. Pašalinus kraštą iš grandinės ar sujungto grafiko, sukuriamas medis, kuris yra medis.
Grafikai yra suskirstyti į įvairias kategorijas, pvz., Nukreiptas, nekreiptas, prijungtas, nesusijęs, paprastas ir daugiagrafinis. Kompiuterinis tinklas, transporto sistema, socialinio tinklo grafikas, elektros grandinės ir projektų planavimas yra grafikos duomenų struktūros taikymas. Jis taip pat naudojamas valdymo technikoje, pavadintoje PERT (programos vertinimo ir peržiūros technika) ir MUT (kritinio kelio metodu), kuriame analizuojama grafiko struktūra.
Grafiko ypatybės:
- Grafo viršūnė gali būti prijungta prie bet kokio skaičiaus kitų viršūnių, naudojant kraštus.
- Kraštas gali būti nukreiptas arba nukreipiamas.
- Briauną galima pasverti.
Grafike taip pat naudojame įvairias sąvokas, tokias kaip gretimos viršūnės, kelias, ciklas, laipsnis, sujungtas grafikas, pilnas grafikas, svertinis grafikas ir tt Suprantame kai kurias iš šių terminų.
- Gretimos viršūnės - viršūnė a yra šalia viršūnės b, jei yra kraštas (a, b) arba (b, a).
- Kelias - kelias iš atsitiktinio viršūnės w yra gretimų viršūnių seka.
- Ciklas - tai kelias, kuriame pirmosios ir paskutinės viršūnės yra tos pačios.
- Laipsnis - tai kraštų skaičius, atsiradęs ant viršūnės.
- Sujungtas grafikas - jei egzistuoja kelias iš atsitiktinio viršūnės į bet kurį kitą viršūnę, tuomet tas grafikas yra žinomas kaip prijungtas grafikas.
Pagrindiniai skirtumai tarp medžio ir grafiko
- Medyje egzistuoja tik vienas kelias tarp dviejų viršūnių, o grafikas gali turėti vienakrypčius ir dvikrypčius kelius tarp mazgų.
- Medyje yra vienas šakninis mazgas, ir kiekvienas vaikas gali turėti tik vieną tėvą. Priešingai, grafike nėra šakninio mazgo koncepcijos.
- Medis negali turėti kilpų ir savarankiškų linijų, o grafikas gali turėti kilpas ir savaimines linijas.
- Grafikai yra sudėtingesni, nes gali turėti kilpų ir savarankiškų linijų. Priešingai, medžiai yra paprasti, palyginti su grafiku.
- Medis perkeliamas naudojant išankstinio užsakymo, užsakymo ir po užsakymo metodus. Kita vertus, naudojant grafiką, mes naudojame BFS (pirmoji paieška) ir DFS (pirmoji paieška).
- Medis gali turėti n-1 kraštus. Priešingai, grafike nėra iš anksto nustatyto kraštų skaičiaus ir tai priklauso nuo grafiko.
- Medis turi hierarchinę struktūrą, o grafikas turi tinklo modelį.
Išvada
Grafikas ir medis yra nelinijinė duomenų struktūra, naudojama įvairioms sudėtingoms problemoms spręsti. Grafikas yra viršūnių ir briaunų grupė, kurioje kraštas jungia viršūnių porą, o medis laikomas minimaliai sujungtu grafu, kuris turi būti sujungtas ir laisvas nuo kilpų.
