基于有向图的程序流程图优化判别方法.pdf

2009年12月 石家庄职业技术学院学报 I)ec．2009 Vocational Institute VOI．2lNO．6 第2l卷第6胡 Joulna|of 7Fechnology Shijiazhuang 文章编号：1009—4873(2009)06—0026—03 基于有向图的程序流程图优化判别方法 梁静坤a， 王丽蕊b (石家庄职业技术学院a．信息工程系；b．经济贸易系，河北石家庄050081) 摘 要：根据有向囝的概念和基本定理，将计算机处理过程中的程序流程图抽象为有向图，用于判别流程图的 逻辑性及是否存在死锁现象，并用实例进行了判别及仿真验证． 关键词：有向图；流程圈；磁共振成像；优化 中图分类号：0157．6 文献标识码：A 图论起源于18世纪，是一支新的数学分支，也 的两个顶点来表示边，如果P边的两个端点是H和 是一门很有实用价值的学科，它在自然科学、社会科 副，那么e可写成P=(“，可)，其中，(M，t，)表示M和 学等领域均有很多应用．图论最早应用于分析电路 秒的无序对，即(“，口)和v，“)都表达了以M和口 网络，随着科学技术的发展，图论在解决运筹学、网 为端点的无向边．图1也可写成G=(V，E)，V= 络理论、信息论、控制论、博弈论以及计算机科学等 {影l，。2，钞3，口4}，E=l(钞l，口2，(秒l，掣3)，(口l， 领域的问题方面发挥了越来越大的作用．…近年 可4)，(口2，口3)，(v2，V4)，(口3，刀4)}． 来，它受计算机科学蓬勃发展的刺激，发展极其迅 V 一般图G=(V，E)的顶点数用恕(=II)表 速，应用范围不断拓广，其应用已经涉及到物理学、 E VI和IE 示，边的数目用肌(=l1)表示．若l 化学、运筹学、计算机科学、信息论、控制论、网络理 都是有限的，则称图G是有限图，否则称为无限图， 论、社会科学以及管理科学等诸多领域．【2J由于图 我们仅讨论有限图的情况． 论方法直观明了、使用方便、容易掌握，已经成为解 决自然科学、工程技术和社会科学等问题的数学工 具，特别是在计算机科学中，如形式语言、数据结构、 分布式系统、操作系统等方面均有重要应用．【3J本 文介绍一种利用有向图的概念，将程序流程图抽象 成有向图，再利用有向图及其度的概念，结合有向图 基本定理，直观地判断流程图的逻辑性是否正确、是 如 否存在死循环的方法，是一种利用数学工具对程序 图1 围的概念 流程图进行优化性判别的方法． 1相关的数学概念及定理【4】 1．2 有向图的概念 1．1图的概念 定义2 图G的边的两个顶点是无序的，一般 定义1 一般几何上将图定义成空间一些点 称为无向图，在实际应用中，将图和每条边分配一个 (顶点)和连接这些点的线(边)的集合．图论中将图方向是很自然的，给图G的每一条边规定一个方 定义为一个偶对G=(V，E)，其中、，表示顶点的向，则称其为有向图．对有向图G=(y，E)，有向 边P用与其关联的顶点l‘，郇的有序对来表示，即 集合，E表示边的集合，如图l，可表示为V={ul， F=(“。御)表示越为边e的起点，口为边P的终点， 可2，