探究网络图的计算机算法和显示方法

刘 晓 飞

(安庆师范大学，安徽 安庆 246133)



探究网络图的计算机算法和显示方法

刘 晓 飞

(安庆师范大学，安徽 安庆 246133)

摘要：信息技术是人类发展的重要助推力，人类社会生产实践中大部分问题的解决都依赖于计算机所构建的数学模型，尤其是针对离散型结构这一问题的解决，计算机数字技术可以充分发挥作用。本文围绕网络图的计算机算法与显示方法展开研究，简要阐述了网络图的基本概念，着重介绍了网络图的计算机算法、显示方法的发展进程，并对其未来发展方向进行分析和展望，以推动该学科的发展。

关键词：网络图；计算机算法；显示方法

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.020

网络图是一种图解模型，主要由作业、事件、路线组成。随着信息时代的到来，网络图已在通信网、工序流程以及电路网路等多个领域得到了广泛应用[1]。网络图能够充分表现项目中各个工序之间相互依赖、相互制约的关系，同时使它们成为一个整体。具体来说，网络图能够形象地表现整个工作计划，在网络图中，可以利用编制程序进行计算，了解到工作的关键，抓住重点矛盾，避免盲目施工。人们可以利用网络图对原始网络中的离散结构及关系等问题进行定量与定性分析，并进一步优化处理；同时根据这些边与边的权值顶点的邻接关系来推断图的连通性和最短路径。

在网络图的实际运用中，不同的计算机算法服务于不同的对象，需要加强对算法的研究，把技术、计算机理论与网络图控制算法相结合，应用于其他领域，让网络图真正为人们所用。

1网络图的控制算法

网络图在生活中运用十分广泛，通过对点符号全控制算法和边符号控制算法的研究与运用，能够得出新的网络图系统。

1.1 点符号全控制算法的发展

点符号基础理论是与全控制算法相结合的一种发展模式。点符号全控制算法融合了符号控制算法这一形式，引入了极限度，并对其最大和最小度进行限定。这种算法在下限过程中，能够实现下界之间的更新过程；在其图像进行中，从下界问题更新这一角度，能够保证满足下界具体的网络图。在网络图全控制算法中，要保证符号具有一定的全面性和完整性。2001年，Zelinka第一次提出符号控制算法的概念。点符号全控制算法作为符号控制算法的一种形式，一直被人们研究、探讨。2003年，刑化明等人给出了点符号全控制算法的下界[2-4]。2004年，MichaelAHenning给出了满足这些下界的具体网络图。2006年，王军秀对点符号全控制算法下界进行了改进，并给出了优于原下界的新下界。2009年，吕新忠等进一步充实了全控制算法的内容。改进后的网络图算法越来越受到学者的关注，需不断地完善和改进。

1.2边符号控制算法的发展

2001年，徐保根提出了边符号控制算法的概念，并丰富、完善了网络图控制算法的内容。2002年，BohdanZelinkaLiberec给出了界限，紧接着徐保根给出了边符号控制算法的上界、下界及部分边符号控制算法数的确切值，随后又完善了边控制算法数的界限。减控制算法是边符号控制算法中的一种，但由于减控制算法研究难度大，研究时间短，因此在这方面还没有太多成果，故研究人员要加强对减控制算法的研究。

1.3点符号、边符号控制算法的发展所带来的影响

点符号和边符号控制算法的发展能构成了一个网络图显示和查询系统，但这种查询系统不稳定，如果对它进行多次修改，很难调出操作的历史记录，同时图像也会显得古板、模糊。因此，对点符号控制算法和边符号控制算法进行改进时要充分发挥数据库的作用，只有这样才能有效解决数据查询难度大的问题。

1.4网络图计算机算法的完善

在网络时代，人们对计算机算法提出了新的要求。2009年，吕新忠和仪明源获得了集中类型特殊网络图的符号全控制算法数，进一步充实了符号全控制算法的内容。其实在更早之前，反符号算法已经得到了实际应用，将反符号算法逐渐发展成为反符号全控制算法，是未来网络图算法的研究重点，也是目前需要关注的内容。此外，在完善边符号算法过程中，一些学者通过研究，获得了部分特殊网络图符号边控制算法数的确切值，得到了一般网络图的界限。根据现有的理论成果和现实条件，边上的减控制算法具有一定的难度，通过研究可以得出，下一步研究的重点是减K边控制算法，应该要把减边控制算法定义中要求满足“全部边” 的条件改作“至少有K条边”，但是该研究同样具有一定的难度，目前该项研究仍在进一步发展中。

此外，人们希望通过对最短路径的研究，在确保算法准确性的同时缩小算法的搜索空间，减轻机器的负荷，提高运行效率，使网络图的计算更加容易。最短路径算法的计算复杂度随着网络规模的变化而变化。由于网络中节点数n与连边数m的增大具有相关性，通常利用降阶的方式构建网络层次化模型，简化网络的拓扑关系，降低算法的复杂度。网络中包含节点和边的数量随着网络分层等级的升高而减少，通过将搜索切换到高层拓扑中能够减少计算过程中节点的数量，达到提高算法运行效率的目的。在最短路径算法中，搜索的盲目性会造成搜索的极大浪费。利用加速引导技术减少计算过程中节点的数量，降低算法的复杂度。搜索策略对于最短路径算法的计算效率和精度的好坏都有重要影响，通过对搜索策略的优化能够获取最快的路径响应速度，提高路径计算精度，降低存储空间的消耗，增强算法的通用性。

2网络图的显示方法及算法

2.1网络图的计算机显示理论基础

网络图的计算机显示理论基础是利用C语言实现网络图的绘制，主要是基于两点原因：一是C语言简洁、功能较大适宜在屏幕上作图；二是利用C语言编写程序所占用的内存相对较少、执行率高[5-6]。在网络图的点连线分析中，常常存在着错综复杂的顶点与边的关系。通常研究人员对网络图进行绘制时会先画出各顶点，接着将各顶点用线连接起来。工作人员在用C语言作图时，采用的是物理坐标，水平方向是X轴，向右为正，向左为负；垂直方向是Y轴，向下为正，向上为负。工作人员在利用坐标(X，Y)表示各点时，X，Y必须是整数且有一定的取值范围。

图形绘制出来后为了让图形的大小、位置适宜，所以需对图形进行缩放、平移、旋转等操作。在完成图的显示算法过程中，常常会控制网络图，添加或删除若干条边、若干个顶点，并在历史查询中详细记录时间。

2.2完成图的显示算法所需的步骤

(1)研究人员通过用户信息在屏幕上绘制出完整的图形。

(2)在输入用户的信息后，根据信息绘制出相应的图像，同时要用不同颜色对新添加的边进行描绘。

(3)通过用户新添加的点构成连通图，用户新添加的信息包括边的信息，最后绘制出图像，要用不同颜色对新添加的顶点和边进行描绘。

(4)在绘制相应的图像时，同时要删除边，边删除后不能有孤立的顶点。

(5)绘制相应的图像时，同时要删除相应的顶点，与顶点相关联的边也要去掉。

(6)对于每次操作都要做好记录，以便日后查询。

(7)对于每次操作都要观测操作的时间。

(8)在构建网络图显示和查询系统时，要考虑图的连通性查询和最短路径查询。

2.3网络图显示图中需注意的问题

工作人员在使用网络图时要注意在输入数据、添加边和添加点时的细节性问题。在输入数据时，首先要输入指令，接着输入相关信息。信息中一般包含了顶点的个数和编号、边的数目和编号、顶点的坐标，最后创建邻接多重表时要将数据输入其中。在输入添加边和顶点时，首先要输入指令，接着输入相关数目，相关数目中包括边的起点与终点个数和新添加顶点的个数，同时要对添加边顶点进行编号， 要对邻接多重表进行修改，最后完成对网络图的绘制。在输入对边和顶点的过程中，要同时进行边与定点的指令添加，输入新添加数目。添加新顶点的过程往往具有孤立性特点，在网络不完整连通情况下，常常要结合基础性环节，对网络图进行基本控制[7-8]。因而，在网络图的计算机算法与实际显示中，是将点符号全控制算法与边符号全控制算法作为基础的，在网络图的实际控制算法应用过程中，要进一步完善网络图的设计，提高计算机算法及显示系统的工作效率[9-10]。

3结语

随着科技的进步，网络图理论也有了较快的发展。网络图理论能够有效地离散事物结构和关系，有助于优化定性或定量层面的问题，同时实现问题的数学化和严谨化。利用点和线来解决、分析问题，把很多解决实际问题的方法回归到建立数学模型中。但是，目前我国工控系统正朝着开放化与智能化方向发展，这在给用户带来巨大便利的同时，也存在一定的安全隐患，例如PLC未对外来数据进行验证、工业以太网有安全漏洞等，如何在完善系统功能、优化操作流程的基础上提高计算机算法的准确性，进而保证工控系统安全，成为一个需要长期探索和研究的课题。计算机技术迅速发展促进了算法理论的控制和发展。未来要加强网络图在计算机网络、拓扑结构和编码理论等领域中的运用，让网络图更好地为人们服务。

参考文献:

[1] 高富.基于网络图的计算机算法分析[J].电子技术与软件工程,2014,54(21):20.

[2] 徐瑾.网络图的计算机算法和显示方法的研究[J].文理导航,2015,45(5)(下旬):6.

[3] 王凌燕.网络图的计算机算法和显示方法的研究[J].电子技术与软件工程,2015,89(1):189-190.

[4] 王莉.网络图的计算机算法和显示方法研究[J].山东农业工程学院学报,2015,56(3):42-43, 46.

[5] 付欣.网络图的计算机算法和显示方法的研究[J].电脑知识与技术,2013,68(35):7946-7947.

[6] 刘乃维.论网络图的计算机算法[J].计算机光盘软件与应用,2014,89(13):95-96.

[7] 吴凯,李鹏,何永强.控制算法理论及网络图计算机算法显示研究[J].现代电子技术,2015,17: 151-152, 157.

[8] 张宏国,王强.CPM网络图计算机自动绘制算法设计[J].信息技术,2001,8:14-16.

[9] 赵建齐.基于并行化的网络图压缩表示算法的研究[D].北京: 北京交通大学, 2014.

[10] 李添捷.生物医学图像融合显示方法的研究[D].上海: 复旦大学,2012.

ComputerAlgorithmandDisplayMethodofNetworkGraph

LIUXiao-fei

(SchoolofComputerandInformation,AnqingNormalUniversity,Anqing,Anhui246133,China)

Abstract:Informationtechnologyisanimportantboostofhumandevelopment.Tosolvethemostproblemsoftheproductionpracticeinhumansocietydependsonthecomputertobuildmathematicalmodel,especiallyfordiscretestructure.Thecomputerdigitaltechnologycanplayavitalroleinsolvingthisproblem.Thispaperfocusesonthecomputeralgorithmofnetworkdiagramanddisplaymethod,brieflyexpoundsthebasicconceptofnetworkdiagram,emphaticallyintroducesthenetworkgraphofcomputeralgorithm,displaysthemethodofthedevelopmentprocess,analyzesandoutlooksitsfuturedevelopmentdirection,whichcanpromotethedevelopmentofthediscipline.

Keywords:Networkdiagram;computeralgorithms;displaymethod

* 收稿日期：2015-09-17

作者简介：刘晓飞，男，山东泰安人，硕士，安庆师范大学副教授，研究方向为计算机软件及相关。E-mail: flyine@vip.qq.com

中图分类号：TP338.8

文献标识码：A

文章编号：1007-4260(2016)02-0086-03

网络出版时间：2016-06-08 12:57网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.020.html