基于网络图的计算机算法

本文从网络图理论中的控制算法理论入手,就网络图的计算机算法进行了简单的阐述.

【关 键 词】网络图计算机算法

自进入信息时代以来,我国科学技术水平得到巨大程度的提升,特别是计算机的发展.而随着人类科学和计算机水平的全面提升,极大地程度上促使了计算机技术和网络图图论之间的紧密结合,特别是在处理离散型结构问题方面.无论在定量还是定性方面上,网络图理论都可以对相关问题进行优化.因此,基于网络图的计算机算法问题已经成为网络图理论中一项重要的研究内容.

1绘制网络图遵循的规则

（1）依据计算机运算的流程和顺序,按照从左向右的排列顺序对其进行施工.

（2）在条件允许的情况下,尽量使用虚工序（不需要人、物力）来表达相邻工序之间的相互链接关系.

（3）网络图中不可以有任何的回路和缺口,无论如何布置,都要确保网络图从始点出发,经过一定的网络路线后均可到达终点.

（4）一个合理的网络图应只包含一个终点和起点.

（5）网络图布局规划.为了使网络图清楚、有序,在对其进行规划过程中,首先,要尽可能地将关键的线路布置在网络图的中间（心）位置；其次,要把相互之间具有联系关系的工作布置在一起；最后,要尽量使用一段水平的折现或者水平线来描述网络图的线路.此外,还可以在网络图上附录时间进度,如果在必要的时候,还可以按照工序来布置网络图.

2计算机算法设计

2.1整体思路

计算机整体算法设计所依据的思路为：通过将具有相互联系的工序的节点设置成同样的编号,并在对数据表进行处理操作过程中,将已知的施工工序通过特定的算法使其与相邻工序的节点进行一一对应,同时使汇点、源点编号呈唯一状态,并要满足上述的网络图的绘制规则；然后将已经处理的节点进行恰当地分级处理,并将联系紧密的节点转化为紧前紧后关系,在这两个特定的接点处需要用线尾加以标识,在箭线的中间部位标出对应工序的代码；对于关键的工序需要用红色来突出显示.

2.2具体算法

为了更好的理解计算机的具体算法,在介绍算法之前,首先介绍几个基本概念.首先,始点工序主要代表网络计划中所允许的、不止一个、最先开工的工序,其具有无紧前工序的特点；其次,所谓的终点工序主要是指在网络计划当中所规定的最后完工工序,具有无紧后工序的特点.

2.2.1网络活动逻辑关系的数字化

所谓的网络活动逻辑关系数字化主要是指在网络图中各个工序之间的节点编号的关系.

（1）确定始点工序的首尾节点编号.

（2）确定始点工序的紧后工序的开始节点编号.

（3）确定中间工序的节点编号.

（4）确定汇点.

2.2.2节点排序

在经过上述四个步骤的处理后,待所有工序的节点都已经赋值完成后,但无需定要确保其始发节点的均要小于结束节点的编号.根据上述的网络图的绘制规则对节点的编号进行恰当地排序.具体的思路为：首先需要找出开始节点的编号大于结束节点的编号n,m,并对所有工序的始发及结束节点进行行之有效的判断,如果其是m则需要将其换为n,而检测如其是n则需要将其换为m,重复该步骤,直至所有存在的工序的节点编号均小于结束节点的编号为止.

2.2.3节点分级

节点的合理布局是网络图绘制好坏的关键.因此,为了确保节点布局顺序的合理性,通常在编制编号的过程中采取先左后右,自上而下的原则来进行编号处理,此外,还需要对节点进行适当的分级,然后将同级节点来进行分层布局.杂计算机进行绘制箭线图和设计的时候,为了保证工序流程的合理性也需要对箭线图中的节点进行适当的分级.

2.2.4网络图绘制

首先,需要确定原点的坐标,然后选取一个适当的载体来绘制出若干个大小相等的圆,其次在用箭线将所绘制出的圆进行串联起来,并要在箭线上面标志出特定的信息,但是要确保所有绘制的圆均是按照特定的规则来进行布局的.

（1）根据上述节点分级的原则进行分级后,为了方便将来的运算,就可以确定各种不同的层次供以画圆,并将每一级的节点数目统计到相应的容器当中.

（2）在每一级上进行圆圈绘制过程中,为了确保圆圈分布的均匀性,需要使每个圆圈之间均相隔一定的距离,即使在同一级上面也需要间隔固定的距离,但是如果每级上面节点的数目不同,则他们之间的距离也各不相同.

（3）为了确定每一级上的圆的间隔,需要根据该级上面节点的数目来进行综合确定.检测如该级上面只有一个节点,则需要将其放置在载体的中间,但是如果某一级上的节点数目呈现出偶数,则需要在纵轴方向（Y方向）上下两方进行布置,反之,如果节点的数目为奇数状态,则需要让它们的纵坐标的本身及其两侧呈现出均匀性的分布状态.

（4）确定节点坐标.鉴于汇点、源点的唯一性,在确定源点的坐标时候,首先需要将横坐标（X）取一个固定的数值,纵坐标Y方向上选取载体高度的一半,然后再确定级次之间的间距N,最后所得到的级次节点的横坐标即为：X+几次*N,而纵坐标的确定则想见步骤c.

（5）在确定节点坐标后,则开始进行圆圈的绘制,在绘制圆圈的时候需要写上该节点的编号.

（6）待上述的五个步骤全部完成后,一张没有箭头标志的网络草图已经基本成型.余下的就需要根据节点及其紧前和紧后节点之间的相互关系来进行箭头的绘制,以表示工序的流向.

（7）为了使网络图更具有实用性,以更便于用户审读网络图,在箭线上还需要标识出工序的有关信息.

3总结

网络图的理论掀起了浓厚的研究,新的理论成果如雨后春笋不断涌现,作为控制算法理论研究的先驱者,我们不仅要在基于网络图的计算机算法理论上进行研究,还应引领那些年轻的学者在浩瀚的研究大海中寻找方向和明确目标.