Steg-för-steg guide till traversala algoritmer i träd och grafer med exempelberäkningar

Traversal algoritmer är avgörande för att utforska träd och grafer i datavetenskap. De hjälper till att besöka alla noder systematiskt för att utföra operationer som att söka, sortera eller analysera strukturer. Denna guide ger en steg-för-steg-översikt över vanliga traversala metoder med exempel beräkningar.

Träd Traversal Algoritmer

Träd traversala algoritmer besöker noder i en viss ordning. De vanligaste metoderna är i ordningen, förbeställningen och efterbeställningstraversalen. Varje tjänar olika ändamål och följer en unik besökssekvens.

In-Order Traversal

I ordningen besöker traversalen vänster subtree, den aktuella noden, sedan den högra subtree. Det används ofta för att hämta data i sorterad ordning från binära sökträd.

Exempel: För ett binärt träd med noder 4, 2, 5, 1, 3, är den i-order traversal sekvensen 1, 2, 3, 4, 5.

Pre-Order Traversal

Förbeställ traversal besöker den nuvarande noden först, sedan vänster subtree, följt av höger subtree. Det är användbart för att kopiera träd eller skapa prefixuttryck.

Exempel: Med samma träd är pre-order-sekvensen 4, 2, 1, 3, 5.

Post-Order Traversal

Efter ordningen besöker den vänstra subtret, den högra subtree, sedan den nuvarande noden. Det används ofta för att ta bort träd eller utvärdera postfixuttryck.

Exempel: För samma träd är efterbeställningssekvensen 1, 3, 2, 5, 4.

Graph Traversal Algoritmer

Graftraversal algoritmer utforska noder i en graf. De två huvudmetoderna är Breadth-First Search (BFS) och Depth-First Search (DFS). De används i nätverksanalys, banfinding och mer.

Bröd-första sökningen (BFS)

BFS utforskar grannar nivå efter nivå, med början från en källnod. Det använder en kö för att hålla reda på noder för att besöka nästa.

Exempel: Från nod A i en graf besöker BFS noder i ordning: A, B, C, D, E, baserat på deras närhet.

Djup-första sökningen (DFS)

DFS utforskar så långt som möjligt längs varje gren innan backtracking. Det använder en stack eller återgång för att hantera traversal.

Exempel: Från nod A kan DFS besöka noder för att: A, B, D, E, C.