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í relací se nazývá graf, zatímco strom je datová struktura, která má sadu uzlů vzájemně propojených.
Graph
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, že každý uzel může být spojen s polem incidentních hran. Pokud mají být informace uloženy spíše v uzlech než v hraná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. Stávající uzly lze propojit přidáním prvků do polí. Ale je tu jedna nevýhoda, protože je potřeba čas, aby se zjistilo, zda mezi uzly existuje hrana.
Jiný způsob, jak toho dosáhnout, je zachovat dvourozměrné pole nebo matici M, která má booleovské hodnoty. Existence hrany od uzlu i do j je specifikována záznamem 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 informatice. Je podobný struktuře stromu a má sadu uzlů, které jsou vzájemně 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 přítomno nula nebo více uzlů. Pokud má uzel potomka, nazývá se nadřazený uzel tohoto potomka. Uzel může být nejvýše jeden rodič. Nejdelší sestupná cesta od uzlu k listu je výška uzlu. Hloubka uzlu je reprezentována cestou k jeho kořenu.
Ve stromu se nejvyšší uzel nazývá kořenový uzel. Kořenový uzel nemá žádné rodiče, protože je nejvýše umístěný. Od tohoto uzlu začínají všechny operace se stromem. 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 interní uzel.
Rozdíl mezi grafem a stromem:
• Strom lze popsat jako specializovaný případ grafu bez vlastních smyček a okruhů.
• Ve stromu nejsou žádné smyčky, zatímco graf může mít smyčky.
• V grafu jsou tři množiny, tj. hrany, vrcholy a množina, která představuje jejich vztah, zatímco strom se skládá z uzlů, které jsou vzájemně propojeny. Tato spojení se označují jako hrany.
• Ve stromu je mnoho pravidel vysvětlujících, jak může docházet ke spojení uzlů, zatímco graf nemá žádná pravidla určující spojení mezi uzly.
