Rozdíl mezi grafem a stromem

Graf vs strom

Graf a strom se používají v datových strukturách. Určitě existují určité rozdíly mezi grafem a stromem. Soubor vrcholů majících binární vztah se nazývá graf, zatímco strom je datová struktura, která má množinu uzlů vzájemně 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. Hrany mohou být znázorněny různými způsoby. Jedním ze způsobů je to, že každý uzel může být spojen s polem dopadajících hran. Pokud mají být informace uloženy v uzlech, nikoli na hranách, pak pole působí 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 připojit přidáním prvků do polí. Jedna nevýhoda však spočívá v tom, že k určení, zda existuje mezera mezi uzly, je nutný čas.

Jiným způsobem, jak toho dosáhnout, je udržet dvourozměrné pole nebo matici M, která má booleovské hodnoty. Existence hrany od uzlu i do j je určena zápisem Mij. Jednou z výhod této metody je zjištění, zda je mezi dvěma uzly nějaká hrana.

Strom

Strom je také datová struktura používaná v informatice. Je podobný struktuře stromu a má množinu uzlů, které jsou vzájemně propojeny.

Uzel stromu může obsahovat podmínku nebo hodnotu. Může to být také strom sám nebo může představovat samostatnou datovou strukturu. Ve stromové struktuře dat jsou přítomny nuly nebo více uzlů. Pokud má uzel dítě, nazývá se jeho nadřazeným uzlem. Může existovat maximálně jeden rodič uzlu. Nejdelší cesta dolů z uzlu do 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čnou všechny stromové operace. Použitím odkazů nebo hran lze získat další uzly z kořenového uzlu. Uzly nejnižší úrovně se nazývají listové uzly a nemají žádné děti. Uzel, který má počet podřízených uzlů, se nazývá vnitřní uzel nebo vnitřní uzel.