Skirtumas tarp medžio ir grafiko
Turinys
Medis ir grafikas priskiriami netiesinių duomenų struktūros kategorijai, kai medis siūlo labai naudingą būdą atvaizduoti ryšį tarp mazgų hierarchinėje struktūroje, o grafikas seka tinklo modelį. Medis ir diagrama skiriasi tuo, kad medžio struktūra turi būti sujungta ir niekada negali turėti kilpų, o diagramoje tokių apribojimų nėra.
Netiesinę duomenų struktūrą sudaro elementų, kurie pasiskirsto plokštumoje, rinkinys, o tai reiškia, kad tarp elementų nėra tokios sekos, kokia ji yra linijinėje duomenų struktūroje.
-
- Palyginimo diagrama
- Apibrėžimas
- Pagrindiniai skirtumai
- Išvada
Palyginimo diagrama
| Palyginimo pagrindas | Medis | Grafikas |
|---|---|---|
| Kelias | Tik viena tarp dviejų viršūnių. | Leidžiamas daugiau nei vienas kelias. |
| Šaknies mazgas | Jis turi tiksliai vieną šaknies mazgą. | Grafike nėra šakninio mazgo. |
| Kilpos | Neleidžiama jokių kilpų. | Grafike gali būti kilpų. |
| Sudėtingumas | Mažiau sudėtinga | Palyginti sudėtingesnis |
| Važiavimo technika | Išankstinis užsakymas, užsakymas ir užsakymas po užsakymo. | Pirma platumo paieška ir pirmo gylio paieška. |
| Briaunų skaičius | n-1 (kur n yra mazgų skaičius) | Neapibrėžtas |
| Modelio tipas | Hierarchinė | Tinklas |
Medžio apibrėžimas
A medis yra baigtinis duomenų elementų, paprastai vadinamų mazgais, rinkinys. Kaip minėta aukščiau, medis yra netiesinė duomenų struktūra, kurioje duomenų elementai išdėstomi rūšiuota tvarka. Jis naudojamas parodyti hierarchinę struktūrą tarp įvairių duomenų elementų ir suskirstyti duomenis į šakas, kurios susieja informaciją. Pridėjus naują briauną medyje, susidaro kilpa ar grandinė.
Yra keli medžių tipai, tokie kaip dvejetainis medis, dvejetainis paieškos medis, AVL medis, dvejetainis medis su sriegiu, B-medis ir kt. Duomenų glaudinimas, failų saugojimas, aritmetinės išraiškos manipuliavimas ir žaidimų medžiai yra keletas medžio taikymo būdų. duomenų struktūra.
Medžio savybės:
- Medžio viršuje yra nurodytas mazgas, žinomas kaip medžio šaknis.
- Likę duomenų elementai yra suskirstyti į atskirtus pogrupius, vadinamus subtree.
- Medis išskleistas aukščio link apačios.
- Medis turi būti sujungtas, tai reiškia, kad turi būti kelias nuo vienos šaknies iki visų kitų mazgų.
- Jame nėra jokių kilpų.
- Medis turi n-1 briaunų.
Su medžiais yra susiję įvairūs terminai, tokie kaip galinis mazgas, kraštas, lygis, laipsnis, gylis, miškas ir kt. Tarp tų terminų kai kurie iš jų aprašyti toliau.
- Briauna - Linija, jungianti du mazgus.
- Lygis - Medis yra padalijamas į lygius taip, kad šaknies mazgas būtų 0 lygio. Tada jo artimiausi vaikai yra 1 lygio, o tiesioginiai jo vaikai yra 2 lygio ir tt iki pat galinio ar lapų mazgo.
- Laipsnis - Tai mazgo pakaitalų skaičius tam tikrame medyje.
- Gylis - Tai didžiausias bet kurio medžio mazgas, dar žinomas kaip ūgio.
- Gnybto mazgas - Aukščiausio lygio mazgas yra galinis mazgas, o kiti mazgai, išskyrus terminalo ir šakninį mazgą, yra žinomi kaip neterminaliniai mazgai.
Grafiko apibrėžimas
A grafikas taip pat yra matematinė netiesinė duomenų struktūra, kuri gali parodyti įvairių rūšių fizinę struktūrą. Jį sudaro viršūnių (arba mazgų) grupė ir briaunų rinkinys, jungiantis dvi viršūnes. Grafiko viršūnės pavaizduotos kaip taškas arba apskritimai, o kraštai - kaip lankai ar linijų segmentai. Briauna pavaizduota E (v, w), kur v ir w yra viršūnių poros. Pašalinus briauną nuo grandinės arba sujungto grafiko, sukuriamas poskyris, kuris yra medis.
Grafikai yra klasifikuojami į įvairias kategorijas, tokias kaip nukreipta, ne nukreipta, sujungta, neprijungta, paprasta ir daugiagrafė. Kompiuterių tinklas, transportavimo sistema, socialinio tinklo grafikas, elektros grandinės ir projekto planavimas yra keletas grafiko duomenų struktūros taikymo būdų. Jis taip pat naudojamas vadybos technikoje, pavadintoje PERTAS (programos įvertinimo ir peržiūros technika) ir MUT (kritinio kelio metodas), kuriame analizuojama grafiko struktūra.
Grafiko savybės:
- Grafiko viršūnė gali būti sujungta su bet kokiu skaičiumi kitų viršūnių, naudojant briaunas.
- Kraštas gali būti nukreiptas arba nukreiptas.
- Briauna gali būti įvertinta.
Grafike taip pat vartojame įvairius terminus, tokius kaip gretimos viršūnės, kelias, ciklas, laipsnis, sujungtas grafikas, visas grafikas, svertinis grafikas ir kt. Supraskime kai kuriuos iš šių terminų.
- Gretimos viršūnės - Viršūnė a yra šalia viršūnės b, jei yra briauna (a, b) arba (b, a).
- Kelias - Kelias iš atsitiktinės viršūnės w yra gretima viršūnių seka.
- Ciklas - Tai yra kelias, kuriame pirmoji ir paskutinė viršūnės yra vienodos.
- Laipsnis - Tai yra keletas briaunų, esančių viršūnėje.
- Prijungtas grafikas - Jei yra kelias iš atsitiktinės viršūnės į bet kurią kitą viršūnę, tada šis grafikas žinomas kaip sujungtas grafikas.
- Medyje yra tik vienas kelias tarp bet kurių dviejų viršūnių, tuo tarpu diagrama tarp mazgų gali turėti vienkryptį ir dvikryptį.
- Medyje yra tiksliai vienas šaknies mazgas, o kiekvienas vaikas gali turėti tik vieną iš tėvų. Grafike nėra šakninio mazgo sąvokos.
- Medis negali turėti kilpų ir kilpų, o schema gali turėti kilpas ir kilpas.
- Grafikai yra sudėtingesni, nes jame gali būti kilpų ir savarankiškų kilpų. Medžiai, priešingai, palyginti su diagrama, yra paprasti.
- Medis apvažiuojamas naudojant išankstinio užsakymo, užsakymo ir po užsakymo būdus. Kita vertus, grafiko perėjimui naudojame BFS (pirmoji platumo paieška) ir DFS (pirmoji gylio paieška).
- Medis gali turėti n-1 briaunų. Grafike, priešingai, nėra iš anksto apibrėžto briaunų skaičiaus, ir tai priklauso nuo grafiko.
- Medis turi hierarchinę struktūrą, o grafikas - tinklo modelį.
Išvada
Grafikas ir medis yra netiesinė duomenų struktūra, naudojama sprendžiant įvairias sudėtingas problemas. Grafikas yra viršūnių ir briaunų grupė, kur briauna jungia viršūnių porą, tuo tarpu medis laikomas minimaliai sujungtu grafiku, kuris turi būti sujungtas ir be kilpų.
