摘要
We revisit a concept that has been central in some early stages of computer science, that of structured programming: a set of rules that an algorithm must follow in order to acquire a certain desirable structure. While much has been written about structured programming, an important issue has been left unanswered: given an arbitrary program, describe an algorithm to decide whether or not it is structured, that is, whether it conforms to the stated principles of structured programming. We refer to a classical concept of structured programming, as described by Dijkstra. By employing graph theoretic techniques, we formulate an efficient algorithm for answering this question. First, we introduce the class of graphs which correspond to structured programs, which we call Dijkstra Graphs. Then we present a greedy O(n)-time algorithm for recognizing such graphs. Furthermore, we describe an isomorphism algorithm for Dijkstra graphs, whose complexity is also linear in the number of vertices of the graph.
摘要译文
我们重新审视了一个在计算机科学的早期阶段，即结构化编程的核心概念：一组算法必须遵循的规则才能获得某种理想的结构。虽然已经有很多关于结构化编程的文章，但是一个重要的问题仍未得到解决：给定一个任意程序，描述一个算法来决定它是否是结构化的，即它是否符合结构化编程的既定原则。我们参考Dijkstra描述的结构化编程的经典概念。通过使用图论技术，我们制定了一个有效的算法来回答这个问题。首先，我们介绍与结构化程序相对应的图形类，我们称之为Dijkstra图形。然后我们提出了一种贪婪的O（n）时间算法来识别这样的图形。此外，我们描述了Dijkstra图的同构算法，其复杂度也是图的顶点数的线性。
Lucila M.S.Bento[b];Davidson R.Boccardo[b];Raphael C.S.Machado[c][d];Flávio K.Miyazawa[f];Vinícius G.Pereira de Sá[a];Jayme L.Szwarcfiter[a][e];. Dijkstra graphs[J]. Discrete Applied Mathematics, 2019,261: 52-62