A nemlineáris adatszerkezet olyan elemek gyűjteményéből áll, amelyek egy síkban vannak elosztva, ami azt jelenti, hogy nincs olyan szekvencia az elemek között, ahogyan egy lineáris adatstruktúrában létezik.
Összehasonlító táblázat
| Az összehasonlítás alapja | Fa | Grafikon |
|---|---|---|
| Pálya | Csak egy két csúcs között. | Több útvonal is megengedett. |
| Gyökér csomópont | Pontosan egy gyökércsomópont van. | A grafikon nem tartalmaz gyökércsomópontot. |
| Loops | Nincs engedélyezett hurok. | A grafikon lehet hurkok. |
| Bonyolultság | Kevésbé összetett | Komplexebb komplexum |
| Átjárási technikák | Előrendelés, rendelés és postai rendelés. | Szélesség-első keresés és mélység-első keresés. |
| Szélek száma | n-1 (ahol n a csomópontok száma) | Nem meghatározott |
| Modell típus | hierarchikus | Hálózat |
A fa meghatározása
A fa az adatelemek véges gyűjteménye, amelyet általában csomópontoknak neveznek. Amint fentebb már említettük, egy fa nemlineáris adatszerkezet, amely rendezett sorrendben az adatelemeket rendezi. Ez arra szolgál, hogy hierarchikus struktúrát mutasson a különböző adatelemek között, és az adatokat fiókokba rendezi, amelyek az információt összekapcsolják. Egy új él hozzáadásával egy fa képezi a hurok vagy áramkör kialakulását.
Számos fafajta létezik, mint például egy bináris fa, bináris keresési fa, AVL fa, menetes bináris fa, B-fa stb. Az adatok tömörítése, a fájltárolás, az aritmetikai kifejezés és a játékfák manipulálása a fa alkalmazásának egy része. adatszerkezet.
A fa tulajdonságai:
- A fa tetején kijelölt csomópont ismert, amely a fa gyökere.
- A fennmaradó adatelemek szétválasztott részhalmazokra vannak osztva, amelyek alrészek.
- A fát magassága az alsó rész felé emelkedik.
- Egy fát kell összekötni, ami azt jelenti, hogy egy gyökérből és az összes többi csomópontból kell lennie.
- Nem tartalmaz hurkot.
- Egy fa n-1 élekkel rendelkezik.
A fákhoz különböző kifejezések tartoznak, mint például a terminál csomópontja, az él, a szint, a fok, a mélység, az erdő stb.
- Edge - Egy vonal, amely két csomópontot köt össze.
- Szint - A fa olyan szintekre van osztva, hogy a gyökércsomópont a 0. szinten legyen. Ezután az ő közvetlen gyermekei az 1. szinten vannak, és közvetlen gyermekei a 2. szinten vannak, és így tovább a terminál vagy a levél csomópontig.
- Fokozat - Ez egy adott fa csomópontjának száma.
- Mélység - Az adott fa bármely csomópontjának maximális szintje, és magasságként is ismert.
- Terminális csomópont - A legmagasabb szintű csomópont a terminál csomópont, míg a többi csomópont, a terminál és a gyökér csomópont kivételével nem-terminális csomópontok.
A grafikon meghatározása
A grafikon egy matematikai nemlineáris adatszerkezet is, amely különböző fizikai struktúrákat képviselhet. A csúcsok (vagy csomópontok) csoportjából és a két csúcsot összekötő élek halmazából áll. A grafikonon lévő pontok pontként jelennek meg, vagy körök és élek jelennek meg az ívek vagy vonalak szegmensek formájában. Egy élet E (v, w) képvisel, ahol v és w a csúcspárok. Egy szegély eltávolítása egy áramkörből vagy egy csatlakoztatott grafikonból egy algráfot hoz létre, amely egy fa.
A grafikonok különböző kategóriákba sorolhatók, például irányított, nem irányított, összekapcsolt, nem kapcsolt, egyszerű és többgrafikus. A számítógépes hálózat, a közlekedési rendszer, a szociális hálózat grafikonja, az áramkörök és a projekttervezés a grafikon adatszerkezetének néhány alkalmazása. Alkalmazzák a PERT (programértékelés és felülvizsgálati technika) és CPM (kritikus útvonal módszer) nevű kezelési technikát is, amelyben a grafikon szerkezetét elemezzük.
A grafikon tulajdonságai:
- A grafikonon lévő csúcsok tetszőleges számú más csúcshoz kapcsolódhatnak élek használatával.
- Egy él átirányítható vagy irányítható.
- Egy él súlyozható.
A grafikonban különböző kifejezéseket használunk, mint például a szomszédos csúcsok, az útvonal, a ciklus, a fok, a kapcsolódó gráf, a teljes grafikon, a súlyozott gráf stb.
- Szomszédos csúcsok - Az a csúcs a b csúcs mellett van, ha van egy él (a, b) vagy (b, a).
- Path - A v egy véletlen csúcsból álló útvonal a csúcsok szomszédos sorozata.
- Ciklus - Ez az út, ahol az első és az utolsó csúcsok azonosak.
- Degree - Ez egy sor csúcs, amely egy csúcson fordul elő.
- Kapcsolódó gráf - Ha van egy útvonal egy véletlen csúcsról bármely más csúcsra, akkor ez a grafikon összekapcsolt gráfként ismert.
A fa és a grafikon közötti különbségek
- Egy fában csak egyetlen út van két csúcs között, míg a gráf egyirányú és kétirányú útvonalakat tartalmazhat a csomópontok között.
- A fában pontosan egy gyökércsomópont van, és minden gyermeknek csak egy szülője van. A grafikonon belül nincs a gyökércsomópont fogalma.
- A fa nem tartalmazhat hurkot és önhurkot, míg a grafikon hurkok és önhurkok lehetnek.
- A grafikonok bonyolultabbak, mivel hurkok és önhurkok lehetnek. Ezzel szemben a fák egyszerűek a grafikonhoz képest.
- A fát előrendelés, rendelés és utólagos technikák segítségével haladják át. Másrészt a grafikon áthaladásához BFS-t (Breadth First Search) és DFS-t (Depth First Search) használunk.
- Egy fa n-1 élekkel rendelkezik. Éppen ellenkezőleg, a grafikonban nincs előre meghatározott számú él, és ez függ a grafikontól.
- A fának hierarchikus szerkezete van, míg a grafikon hálózati modellt tartalmaz.
Következtetés
A grafikon és a fa a nemlineáris adatstruktúra, amelyet különböző komplex problémák megoldására használnak. A gráf olyan csúcsok és élek csoportja, ahol egy él egy csúcspontot köt össze, míg a fát minimálisan összekapcsolt gráfnak kell tekinteni, amelyet összekötni és szabadon kell tartani a hurkoktól.
