Starpība starp koku un grafiku

• 2019

Koks un grafiks nonāk nelineārās datu struktūras kategorijā, kur koks piedāvā ļoti noderīgu veidu, kā attēlot attiecības starp mezgliem hierarhiskā struktūrā, un grafiks seko tīkla modelim. Koks un grafiks tiek diferencēts ar to, ka koku struktūrai jābūt savienotai un nekad nevar būt cilpas, bet grafikā nav šādu ierobežojumu.

Nelineārā datu struktūra sastāv no elementu kolekcijas, kas ir sadalītas plaknē, kas nozīmē, ka starp elementiem nav tādas secības, kāda pastāv lineārā datu struktūrā.

Salīdzinājuma diagramma

Salīdzināšanas pamats	Koks	Grafiks
Ceļš	Tikai viena no divām virsotnēm.	Ir atļauts vairāk nekā viens ceļš.
Sakņu mezgls	Tam ir tieši viens saknes mezgls.	Diagrammā nav saknes mezgla.
Cilpas	Nav atļautas cilpas.	Grafikā var būt cilpas.
Sarežģītība	Mazāk sarežģīts	Salīdzinoši sarežģītāka
Pārvietošanās paņēmieni	Pre-order, In-order un Post-order.	Pirmā meklēšana un dziļuma pirmā meklēšana.
Malu skaits	n-1 (kur n ir mezglu skaits)	Nav definēts
Modeļa tips	Hierarhisks	Tīkls

Koka definīcija

Koks ir ierobežots datu vienību kopums, ko parasti sauc par mezgliem. Kā jau iepriekš minēts, koks ir nelineāra datu struktūra, kas sakārto kārtībā datu elementus. To izmanto, lai parādītu hierarhisku struktūru starp dažādiem datu elementiem un organizē datus filiālēs, kas saistītas ar informāciju. Jaunas malas pievienošana kokam rada cilpas vai ķēdes veidošanos.

Ir vairāki koku veidi, piemēram, binārs koks, binārs meklēšanas koks, AVL koks, vītņots binārs koks, B-koks, utt. datu struktūra.

Koka īpašības:

• Koka augšpusē ir norādīts mezgls, kas pazīstams kā koka sakne.
• Atlikušie datu posteņi ir sadalīti dalītās apakšgrupās, kas minētas kā apakšsekcija.
• Koku aug augstumā uz leju.
• Jābūt savienotam kokam, kas nozīmē, ka ir jābūt ceļam no viena saknes uz visiem citiem mezgliem.
• Tā nesatur cilpas.
• Kokam ir n-1 malas.

Ir dažādi termini, kas saistīti ar kokiem, piemēram, termināla mezglu, malu, līmeni, pakāpi, dziļumu, mežu utt.

• Edge - līnija, kas savieno divus mezglus.
• Līmenis - koks tiek sadalīts līmeņos tādā veidā, ka saknes mezgls ir 0. līmenī. Tad tās tiešie bērni atrodas 1. līmenī, un tā tiešie bērni atrodas 2. līmenī un līdz pat galam vai lapu mezglam.
• Grāds - tas ir mezgla apakšgrupu skaits noteiktā kokā.
• Dziļums - tas ir jebkura mezgla maksimālais līmenis noteiktā kokā un pazīstams arī kā augstums .
• Termināla mezgls - augstākā līmeņa mezgls ir gala mezgls, bet citi mezgli, izņemot terminālu un sakņu mezglu, ir pazīstami kā ne-terminālie mezgli.

Grafika definīcija

Grafiks ir arī matemātiska nelineāra datu struktūra, kas var pārstāvēt dažāda veida fizisko struktūru. Tas sastāv no virsotņu (vai mezglu) grupas un malām, kas savieno divas virsotnes. Vertikāli grafikā ir attēloti kā punkti vai apļi un malas tiek parādītas kā loki vai līniju segmenti. Malu pārstāv E (v, w), kur v un w ir virsotņu pāri. Malu noņemšana no ķēdes vai savienotas diagrammas rada apakšgrupu, kas ir koks.

Diagrammas tiek iedalītas dažādās kategorijās, piemēram, virzienā, nav virzītas, savienotas, nav savienotas, vienkāršas un vairāku grafiku. Datoru tīkls, transporta sistēma, sociālo tīklu grafiks, elektriskās ķēdes un projektu plānošana ir daži no grafu datu struktūras lietojumiem. To izmanto arī vadības paņēmienā, kas nosaukta par PERT (programmas novērtēšana un pārskatīšanas metode) un MPT (kritiskā ceļa metode), kurā tiek analizēta diagrammas struktūra.

Diagrammas rekvizīti:

• Grafa virsotni var savienot ar jebkuru citu virsotņu skaitu, izmantojot malas.
• Malu var divvirzīt vai virzīt.
• Malu var svērt.

Grafikā mēs izmantojam arī dažādus terminus, piemēram, blakus esošos virsotnes, ceļu, ciklu, pakāpi, savienoto grafiku, pilnīgu grafiku, svērto grafiku utt.

• Blakus esošās virsotnes - virsotne a atrodas blakus virsotnei b, ja ir mala (a, b) vai (b, a).
• Ceļš - ceļš no izlases virsotnes w ir blakus esošo virsotņu secība.
• Cikls - tas ir ceļš, kurā pirmie un pēdējie virsotnes ir vienādi.
• Grāds - tas ir vairāku malu skaits, kas notiek virsotnē.
• Savienots grafiks - ja pastāv ceļš no izlases virsotnes uz jebkuru citu virsotni, tad šis grafiks ir pazīstams kā savienots grafiks.

Galvenās atšķirības starp koku un grafiku

1. Kokā pastāv tikai viens ceļš starp jebkurām divām virsotnēm, bet grafikā var būt vienvirziena un divvirzienu ceļi starp mezgliem.
2. Kokā ir tieši viens saknes mezgls, un katram bērnam var būt tikai viens vecāks. Pretstatā, grafikā nav saknes mezgla jēdziena.
3. Kokam nevar būt cilpas un pašcilvēki, bet grafikā var būt cilpas un pašlīnijas.
4. Grafiki ir sarežģītāki, jo tiem var būt cilpas un pašlīnijas. Turpretī koki ir vienkārši, salīdzinot ar grafiku.
5. Koku šķērso, izmantojot iepriekšēja pasūtījuma, pēc kārtas un pēc pasūtījuma. No otras puses, izmantojot grafiku, mēs izmantojam BFS (visplašāko meklēšanu) un DFS (pirmā meklēšana pēc dziļuma).
6. Kokam var būt n-1 malas. Gluži pretēji, grafikā nav iepriekš definētu malu skaita, un tas ir atkarīgs no grafika.
7. Kokam ir hierarhiska struktūra, bet grafam ir tīkla modelis.

Secinājums

Grafiks un koks ir nelineāra datu struktūra, ko izmanto dažādu sarežģītu problēmu risināšanai. Grafiks ir virsotņu un malu grupa, kur mala savieno pāri virsotnēm, bet koku uzskata par minimāli savienotu grafiku, kam jābūt savienotam un brīvam no cilpām.