Как рассчитать все возможные перестановки для древовидной диаграммы

Question

У меня проблема с диаграммой, которая представляет городские дороги, и мне нужно рассчитать все возможные пути - перестановки - чтобы установить эти дороги.

Роль "Вы не можете начать уровень 2 без завершения уровня 1" и так далее для более высоких уровней

это изображение иллюстрирует идею здесь

Я пытался представить его как массив для каждого уровня, а затем по одному столбцу для каждой ветви, как это

level1=[1 2]
level2=[3 4
        5 6]

и л

;evel1=[1 2 3]
level2=[4 5 0; 
       6 7 8; 
       9 10 0]
level3=[11 12;
13 0;
14 15;
16 17;
0 0;
0 0;
18 19]

Но я остановился и понятия не имею, как это сделать. поэтому мне нужно знать, как думать в такого рода проблемах.

Answer 1

Вам следует изучить концепцию «абстрактных типов данных», поскольку ваш текущий дизайн не будет масштабироваться. Каждый раз, когда вы добавляете новый уровень, вам нужно создать новый массив, а затем обновить свой код, чтобы узнать об этом новом массиве.

И процесс поиска одного уровня перед переходом на следующий известен как поиск в ширину. Если вы создаете тип списка, вы можете добавить все узлы текущего уровня в список, а затем, когда вы обрабатываете список, вы добавляете дочерние узлы в конец списка.

Но это не совсем применимо для генерации всех перестановок - выполнение «сначала глубины» более подходит, когда вы путешествуете по дереву и когда вы не можете идти дальше, выбранный вами путь - перестановка.