Tartalom

• Összehasonlító táblázat
• A fa meghatározása
• A fa tulajdonságai:
• A grafikon meghatározása
• A grafikon tulajdonságai:
• Következtetés

A fa és a gráf a nemlineáris adatszerkezet kategóriájába tartozik, ahol a fa nagyon hasznos módot jelent a csomópontok közötti kapcsolat hierarchikus struktúrában való ábrázolására, a gráf pedig egy hálózati modellt követ. A fát és a gráfot megkülönbözteti az a tény, hogy a fa szerkezetét össze kell kötni, és soha nem lehetnek hurkok, míg a grafikonon nincs ilyen korlátozás.

A nemlineáris adatszerkezet egy síkban elosztott elemgyűjteményből áll, ami azt jelenti, hogy az elemek között nincs ilyen sorrend, mint egy lineáris adatszerkezetben.

1. 1. Összehasonlító táblázat
   2. Meghatározás
   3. Főbb különbségek
   4. Következtetés

Összehasonlító táblázat

Az összehasonlítás alapja	Fa	Grafikon
Pálya	Csak egy a két csúcs között.	Egynél több út megengedett.
Gyökér csomópont	Pontosan egy gyökér csomópont van.	A grafikonnak nincs gyökér csomópontja.
Loops	Nincs hurok használata.	A grafikon hurkokat tartalmazhat.
Bonyolultság	Kevésbé összetett	Összetettebben összehasonlítva
Átmeneti technikák	Előrendelés, megrendelés és utórendelés.	Szélesség-első és mély-első keresés.
Élek száma	n-1 (ahol n a csomópontok száma)	Nem meghatározott
Modell típusa	hierarchikus	Hálózat

A fa meghatározása

A fa az adat elemek véges gyűjteménye, amelyeket általában csomópontoknak neveznek. Mint fentebb említettük, egy fa nemlineáris adatszerkezet, amely az adatelemeket rendezett sorrendbe rendezi. Hierarchikus struktúrának a bemutatására szolgál a különféle adatelemek között, és az adatokat olyan ágakba rendezi, amelyek az információt összekapcsolják. Egy új él hozzáadása a fához a hurok vagy áramkör kialakulásához vezet.

Különféle fafajták léteznek, például bináris fa, bináris kereső fa, AVL fa, menetes bináris fa, B-fa stb. Az adatok tömörítése, fájl tárolása, a számtani kifejezés manipulálása és a játékfák a fa alkalmazásának néhány példája. adatszerkezet.

A fa tulajdonságai:

• A fa tetején van egy kijelölt csomópont, amelyet a fa gyökérének hívnak.
• A fennmaradó adatelemeket szétválasztott alcsoportokra osztják, amelyek részfára hivatkoznak.
• A fa magassága meghosszabbodik az alja felé.
• A fát össze kell kötni, ami azt jelenti, hogy útnak kell lennie az egyik gyökér és a többi csomópont között.
• Nem tartalmaz hurkokat.
• Egy fa n-1 élű.

A fákkal kapcsolatban különféle kifejezések vannak, például terminál csomópont, él, szint, fok, mélység, erdő stb. Ezek között a kifejezések közül néhányat az alábbiakban ismertetünk.

• Él - Két csomópontot összekötő vonal.
• Szint - Egy fa fel van osztva szintekre úgy, hogy a gyökér csomópont 0-as szinten legyen. Ezután közvetlen gyermekei az 1. szinten vannak, a közvetlen gyermekeik pedig a 2. szinten és így tovább, a terminál vagy a levél csomópontjáig.
• Fokozat - Ez egy adott fa csomópontjának alfák száma.
• Mélység - Ez egy adott fa bármely csomópontjának maximális szintje, más néven magasság.
• Terminál 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ópontokként ismert.

A grafikon meghatározása

A grafikon egy matematikai nemlineáris adatszerkezet, amely különféle fizikai struktúrákat képviselhet. Csúcsok (vagy csomópontok) csoportjából és élekből áll, amelyek összekötik a két csúcsot. A grafikon csúcsait pontokkal vagy körökkel, az éleket ívekkel vagy vonalszakaszokkal ábrázoljuk. Az éleket E (v, w) jelöli, ahol v és w a csúcspárok. Az élek eltávolítása egy áramkörtől vagy a csatlakoztatott gráftól alsávot hoz létre, amely egy fa.

A grafikonokat különféle kategóriákba sorolhatjuk, mint például irányított, nem irányított, csatlakoztatott, nem csatlakoztatott, egyszerű és több gráf. A számítógépes hálózat, a szállítási rendszer, a közösségi hálózati gráf, az elektromos áramkörök és a projekttervezés a gráf-adatszerkezet néhány alkalmazása. A menedzsment technikában szintén alkalmazzák HETYKE (programértékelési és áttekintési technika) és CPM (kritikus út módszer), amelyben a gráf szerkezetét elemzik.

A grafikon tulajdonságai:

• A gráf csúcsa tetszőleges számú csúcshoz kapcsolható élek segítségével.
• Az él lehet irányítva vagy irányítva.
• Egy él súlyozható.

A gráfban különféle kifejezéseket használunk, például szomszédos csúcsokat, útvonalat, ciklust, fokot, összekapcsolt gráfot, teljes gráfot, súlyozott gráfot stb. Megértjük ezeknek a kifejezéseknek a néhányát.

• Szomszédos csúcsok - Az a csúcs szomszédos a b csúccsal, ha van (a, b) vagy (b, a) él.
• Pálya - A véletlenszerű w csúcsból származó út egy szomszédos csúcsok sorozata.
• Ciklus - Ez egy olyan út, ahol az első és az utolsó csúcs megegyezik.
• Fokozat - Ez egy csúcson eső élek száma.
• Csatlakoztatott grafikon - Ha létezik egy út egy véletlenszerű csúcsból bármely más csúcshoz, akkor ezt a gráfot összekapcsolt gráfnak nevezzük.

1. Egy fában két csúcs között csak egy út létezik, míg a gráfnak lehet egyirányú és kétirányú útja a csomópontok között.
2. A fában pontosan egy gyökér csomópont van, és minden gyermeknek csak egy szülő lehet. Ezzel szemben egy gráfban nincs fogalom a gyökér csomópontról.
3. Egy fa nem tartalmazhat hurkokat és önhurkokat, míg a grafikon hurkokat és önhurkokat tartalmazhat.
4. A grafikonok összetettebbek, mivel hurkokkal és önhurkokkal is rendelkezhetnek. Ezzel szemben a fák egyszerűek a grafikonhoz képest.
5. A fát előrendelési, rendelési és utórendelési technikákkal hajtják át. Másrészt a gráfok áthaladásához BFS-t (szélesség első keresése) és DFS-t (első mélység keresés) használunk.
6. Egy fa n-1 élű lehet. Éppen ellenkezőleg, a gráfban nincs előre megadott számú él, és ez függ a gráftól.
7. Egy fa hierarchikus felépítésű, míg a gráf hálózati modellt tartalmaz.

Következtetés

A gráf és a fa a nemlineáris adatszerkezet, amelyet különféle komplex problémák megoldására használnak. A gráf csúcsok és élek egy csoportja, ahol egy él egy csúcsot kapcsol össze, míg a fát minimálisan összekapcsolt gráfnak tekintik, amelyet össze kell kötni és hurkoktól mentesnek kell lennie.