Was es mit der bei der Tiefensuche beschriebenen "einfachen Implementierbarkeit des backtracking bei der Tiefensuche" auf sich hat, wird erst deutlich, wenn man ausgehend von der Tiefensuche, bei der man das backtracking vom System mit Hilfe des Systemstacks hat ausführen lassen, nun versucht, mit demselben Programm, beispielsweise durch einfaches Umstellen der Aufrufe, eine Breitensuche durchzuführen.
Es zeigt sich sehr schnell, dass dies nicht zu einer Breitensuche führt, sondern nur zu einer Suche, bei der zwar erst alle Alternativen konkret untersucht werden, dann aber nach dem Abstieg in die Tiefe erst in diesem Ast alle weiteren Möglichkeiten untersucht werden, dann davon wieder nur ein Ast usw. und erst nach einem backtracking die Alternativen weiter versucht werden.
So werden aber nicht alle Alternativen in gleicher Breite angegangen. Wenn man dies will, geht das nur mit einer
anderen allgemeinen Datenstruktur als der des stacks |
Um die Notwendigkeit einer Umarbeitung vorzubereiten und um zu verstehen, was überhaupt im Systemstack geschieht, sollte man zunächst einmal diese Verwaltung des stacks bei der Tiefensuche selbst durchführen.
Danach sollte die notwendig neue Organisation der Datenstruktur bei der Breitensuche leichter verständlich sein.