c - 如何计算树形图的所有可能排列

Question

我有一个代表城市道路的三通图问题，需要计算所有可能的方式 - 排列 - 来建立这些道路。

角色是“你不能在没有完成第 1 关的情况下开始第 2 关”等等更高的关卡

这张图片说明了这里的想法

我试图将其视为每个级别的数组，然后像这样的每个分支的单个列

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]

但我停了下来，不知道如何完成。所以我需要知道如何思考这类问题。

标签： calgorithmsortingpermutation

Answer 1

您应该研究“抽象数据类型”的概念，因为您当前的设计不会扩展。每次添加新关卡时，您都需要创建一个新数组，然后更新您的代码以了解这个新数组。

在进入下一个级别之前搜索一个级别的过程称为“广度优先”搜索。如果创建列表类型，则可以将当前级别的所有节点添加到列表中，然后在处理列表时，将子节点添加到列表的末尾。

但这并不真正适用于生成所有排列——当你沿着树向下移动时，做“深度优先”更合适，当你不能再往前走时，你所走的路径就是一个排列。