algorithm - 流程图的可证明平面性

Question

我有一个问题:是否有任何引用资料(例如论文)证明流程图布局的平面性？谁能建议一种生成流程图(平面)布局的算法？

我知道有一些代码到流程图的工具，但我不知道它们的内部结构。

Answer 1

我不同意 Hooked。流程图，有一些限制(使用循环是不是其中之一)，是平面的。一些例子:

• 单个原始命令转换为平面图(单个节点)
• 语句序列:如果语句可以转换为平面图，则序列本身也可以转换为平面图(只需连接这些子图)
• A函数:同上
• (repeat-until、while-do 等)循环是形成循环的语句序列。循环也很好，只要它们正确嵌套(这样的构造被设计为正确嵌套)。
• Goto 语句(goto，或break/continue/return 可能跳转的语句)是不好吧。如果您有一个嵌套循环，并且从内部跳出外部循环，那么这样的边将明显与包含它的循环(循环，函数)相交。如果代码被翻译成一次退出一个循环，这些也很好。 (这种翻译与简单地引入节点来为交叉路口建模并没有太大区别)。

必须有一种更系统的方法来正式证明从一组特定构造的组合派生的流程图是平面的，我希望我能在 5 分钟内想到它，但运气不好 :)

更新:顺便说一句，gotos 可以简单地创建一个 K3、3 或 K5，例如这是一个 K5(在老式的 QBasic 中!) :

00 GOTO (INT(RND * 5) * 10) 
10 GOTO (INT(RND * 5) * 10)
20 GOTO (INT(RND * 5) * 10)
30 GOTO (INT(RND * 5) * 10)
40 GOTO (INT(RND * 5) * 10)