Rozdíl Mezi Grafem A Stromem

2024 Autor: Mildred Bawerman | [email protected]. Naposledy změněno: 2023-12-16 08:37

Graf vs. strom

Graf a strom se používají v datových strukturách. Mezi Graph a Tree určitě existují určité rozdíly. Sada vrcholů s binárním vztahem se nazývá graf, zatímco strom je datová struktura, která má sadu uzlů navzájem propojených.

Graf

Graf je sada položek, které jsou spojeny hranami a každá položka je známá jako uzel nebo vrchol. Jinými slovy, graf lze definovat jako množinu vrcholů a mezi těmito vrcholy existuje binární vztah.

Při implementaci grafu jsou uzly implementovány jako objekty nebo struktury. Okraje lze znázornit různými způsoby. Jedním ze způsobů je, že každý uzel může být přidružen k poli dopadajících hran. Pokud mají být informace uloženy v uzlech spíše než na okrajích, pak pole fungují jako ukazatele na uzly a také představují hrany. Jednou z výhod tohoto přístupu je, že do grafu lze přidat další uzly. Existující uzly lze propojit přidáním prvků do polí. Existuje však jedna nevýhoda, protože je zapotřebí čas k určení, zda je mezi uzly hrana.

Jiným způsobem je zachovat dvourozměrné pole nebo matici M, která má logické hodnoty. Existence hrany z uzlu i do j je specifikována položkou Mij. Jednou z výhod této metody je zjistit, zda je mezi dvěma uzly nějaká hrana.

Strom

Strom je také datová struktura používaná v počítačové vědě. Je to podobné jako struktura stromu a má sadu uzlů, které jsou navzájem propojeny.

Uzel stromu může obsahovat podmínku nebo hodnotu. Může to být také vlastní strom nebo může představovat samostatnou datovou strukturu. Ve stromové datové struktuře je nula nebo více uzlů. Pokud má uzel dítě, pak se nazývá nadřazený uzel tohoto dítěte. Může existovat maximálně jeden rodič uzlu. Nejdelší cestou dolů od uzlu k listu je výška uzlu. Hloubku uzlu představuje cesta k jeho kořenu.

Ve stromu se nejvyšší uzel nazývá kořenový uzel. Kořenový uzel nemá žádné rodiče, protože je nejvyšší. Z tohoto uzlu začínají všechny operace se stromy. Pomocí odkazů nebo hran lze z kořenového uzlu dosáhnout dalších uzlů. Uzly na nejnižší úrovni se nazývají listové uzly a nemají žádné potomky. Uzel, který má počet podřízených uzlů, se nazývá vnitřní uzel nebo vnitřní uzel.

• Strom lze popsat jako speciální případ grafu bez vlastních smyček a obvodů.

• Ve stromu nejsou žádné smyčky, zatímco graf může mít smyčky.

• V grafu jsou tři sady, tj. Hrany, vrcholy a sada, která představuje jejich vztah, zatímco strom se skládá z uzlů, které jsou navzájem spojeny. Tato spojení se označují jako hrany.

• Ve stromu existuje řada pravidel vysvětlujících, jak může dojít k připojení uzlů, zatímco graf nemá žádná pravidla určující spojení mezi uzly.