Algorithmus von Walker
Der Algorithmus von Walker ist ein Reglement zum Zeichnen von Bäumen in der Graphentheorie.
Der Algorithmus basiert auf der geschichteten Zeichnung des Baumes (Layered Drawings). Dabei ergibt sich die Y-Koordinate eines jeden Knoten des Baumes direkt aus der Tiefe des Knotens. Dadurch muss bei diesem Algorithmus nur die X-Koordinate des jeweiligen Knotens in der Zeichnung bestimmt werden.
Die Laufzeit des Algorithmus ist, anders als ursprünglich vermutet, nicht linear, sondern quadratisch abhängig von der Anzahl der Knoten. Es existiert jedoch eine Verbesserung des Algorithmus von Christoph Buchheim et al., der eine lineare Laufzeit ermöglicht.
Literatur
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}