Atšķirība starp koku un grafiku
Saturs
Koks un grafiks ietilpst nelineāru datu struktūras kategorijā, kur koks piedāvā ļoti noderīgu veidu, kā attēlot attiecības starp mezgliem hierarhiskā struktūrā, un diagramma seko tīkla modelim. Koku un grafiku atšķir tas, ka koka struktūrai jābūt savienotai un tajā nekad nedrīkst būt cilpas, kamēr grafikā nav šādu ierobežojumu.
Nelineārā datu struktūra sastāv no to elementu kolekcijas, kas tiek sadalīti plaknē, kas nozīmē, ka starp elementiem nav šādas secības, kā tas pastāv lineārā datu struktūrā.
-
- Salīdzināšanas tabula
- Definīcija
- Galvenās atšķirības
- Secinājums
Salīdzināšanas tabula
| Salīdzināšanas pamats | Koks | Grafiks |
|---|---|---|
| Ceļš | Tikai viena starp divām virsotnēm. | Ir atļauts vairāk nekā viens ceļš. |
| Saknes mezgls | Tam ir tieši viens saknes mezgls. | Grafim nav saknes mezgla. |
| Cilpas | Nav atļauts izmantot cilpas. | Diagrammai var būt cilpas. |
| Sarežģītība | Mazāk sarežģīti | Salīdzinoši sarežģītāka |
| Šķērsošanas paņēmieni | Iepriekš pasūtīt, pasūtīt un pēc pasūtījuma. | Pirmais plašums un pirmais dziļums. |
| Malu skaits | n-1 (kur n ir mezglu skaits) | Nav definēts |
| Modeļa tips | Hierarhiska | Tīkls |
Koka definīcija
A koks ir ierobežots datu vienumu apkopojums, ko parasti sauc par mezgliem. Kā minēts iepriekš, koks ir nelineāra datu struktūra, kas sakārto datu vienumus sakārtotā secībā. To izmanto, lai parādītu hierarhisku struktūru starp dažādiem datu elementiem un sakārtotu datus nozarēs, kas attiecas uz informāciju. Jaunu malu pievienojot kokam, veidojas cilpa vai ķēde.
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 saspiešana, failu glabāšana, manipulācijas ar aritmētisko izteiksmi un spēles koki ir daži no koka izmantošanas veidiem. datu struktūra.
Koka īpašības:
- Koka augšdaļā ir noteikts mezgls, ko sauc par koka sakni.
- Atlikušie datu vienumi ir sadalīti nesadalītās apakšgrupās, kas tiek sauktas par apakštrīsēm.
- Koks ir paplašināts augstumā virzienā uz dibenu.
- Kokam jābūt savienotam, kas nozīmē, ka ir jābūt ceļam no vienas saknes uz visiem citiem mezgliem.
- Tajā nav cilpu.
- Kokam ir n-1 malas.
Ar kokiem ir saistīti dažādi termini, piemēram, gala mezgls, mala, līmenis, pakāpe, dziļums, mežs utt. Starp šiem terminiem daži no tiem aprakstīti zemāk.
- Mala - līnija, kas savieno divus mezglus.
- Līmenis - Koks tiek sadalīts līmeņos tā, lai saknes mezgls būtu 0. līmenī. Tad tā tiešie bērni ir 1. līmenī, bet tā tiešie bērni ir 2. līmenī un tā tālāk līdz termināla vai lapas mezglam.
- Grāds - Tas ir mezgla apakšlīmju skaits dotajā kokā.
- Dziļums - Tas ir jebkura koka mezgla maksimālais līmenis un pazīstams arī kā augums.
- Termināla mezgls - Augstākā līmeņa mezgls ir termināla mezgls, savukārt citi mezgli, izņemot terminālu un saknes mezglu, ir zināmi kā terminālu mezgli.
Grafika definīcija
A grafiks ir arī matemātiska nelineāra datu struktūra, kas var attēlot dažāda veida fizisko struktūru. Tas sastāv no virsotņu grupas (vai mezgliem) un malu kopas, kas savieno abas virsotnes. Grafika virsotnes tiek attēlotas kā punkts vai apļi, un malas tiek parādītas kā loka vai līnijas segmenti. Malu apzīmē ar E (v, w), kur v un w ir virsotņu pāri. Malas noņemšana no shēmas vai savienota grafika izveido apakšgrāfu, kas ir koks.
Grafikus klasificē dažādās kategorijās, piemēram, virzītās, nevirzītās, savienotās, nesaistītās, vienkāršās un vairāku grafiku diagrammas. Datortīkls, transporta sistēma, sociālā tīkla grafiks, elektriskās shēmas un projekta plānošana ir daži no grafika datu struktūras pielietojumiem. To izmanto arī vadības tehnikā, ko sauc par PERT (programmas novērtēšanas un pārskatīšanas tehnika) un MPT (kritiskā ceļa metode), kurā tiek analizēta grafika struktūra.
Diagrammas īpašības:
- Diagrammas virsotni var savienot ar jebkuru citu virsotņu skaitu, izmantojot malas.
- Apmali var virzīt vai virzīt.
- Apmali var svērt.
Arī grafikā mēs izmantojam dažādus terminus, piemēram, blakus esošās virsotnes, ceļu, ciklu, pakāpi, savienoto diagrammu, pilnīgu grafiku, svērto grafiku utt. Izpratīsim dažus no šiem terminiem.
- Blakus esošās virsotnes - Virkne a atrodas blakus virsotnei b, ja ir mala (a, b) vai (b, a).
- Ceļš - Ceļš no nejaušas virsotnes w ir blakus esoša virsotņu secība.
- Cikls - Tas ir ceļš, kurā pirmā un pēdējā virsotne ir vienāda.
- Grāds - Tā ir virkne malu, kas atrodas virsotnē.
- Pievienotais grafiks - Ja pastāv ceļš no nejaušas virsotnes uz jebkuru citu virsotni, tad šo grafiku sauc par savienotu diagrammu.
- Kokā ir tikai viens ceļš starp jebkurām divām virsotnēm, turpretim grafam starp mezgliem var būt vienvirziena un divvirzienu ceļi.
- Kokā ir tieši viens saknes mezgls, un katram bērnam var būt tikai viens vecāks. Grafikā nav saknes mezgla jēdziena.
- Kokam nevar būt cilpas un pašcilpas, savukārt grafikā var būt cilpas un pašcilpas.
- Grafiki ir sarežģītāki, jo tajā var būt cilpas un pašcilpas. Turpretī koki, salīdzinot ar diagrammu, ir vienkārši.
- Koks tiek šķērsots, izmantojot priekšpasūtīšanas, pasūtīšanas un pēcpasūtīšanas paņēmienus. No otras puses, grafika šķērsošanai mēs izmantojam BFS (pirmā platuma meklēšana) un DFS (pirmā dziļuma meklēšana).
- Kokam var būt n-1 malas. Gluži pretēji, grafikā nav iepriekš noteikta malu skaita, un tas ir atkarīgs no grafika.
- Kokam ir hierarhiska struktūra, savukārt grafam ir tīkla modelis.
Secinājums
Diagramma un koks ir nelineāra datu struktūra, ko izmanto dažādu sarežģītu problēmu risināšanai. Diagramma ir virsotņu un malu grupa, kurā mala savieno virsotņu pāri, turpretī koks tiek uzskatīts par minimāli savienotu grafu, kam jābūt savienotam un bez cilpām.
