基于網絡圖的計算機算法分析

高富

本文從網絡圖理論中的控制算法理論入手，就網絡圖的計算機算法進行了簡單的闡述。

【關鍵詞】網絡圖 計算機 算法

自進入信息時代以來，我國科學技術水平得到巨大程度的提升，特別是計算機的發展。而隨著人類科學和計算機水平的全面提升，極大地程度上促使了計算機技術和網絡圖圖論之間的緊密結合，特別是在處理離散型結構問題方面。無論在定量還是定性方面上，網絡圖理論都可以對相關問題進行優化。因此，基于網絡圖的計算機算法問題已經成為網絡圖理論中一項重要的研究內容。

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 總結

網絡圖的理論掀起了濃厚的研究高潮，新的理論成果如雨后春筍不斷涌現，作為控制算法理論研究的先驅者，我們不僅要在基于網絡圖的計算機算法理論上進行研究，還應引領那些年輕的學者在浩瀚的研究大海中尋找方向和明確目標。

參考文獻

[1] 張彩慶，王婷.網絡圖自動生成算法研究[J].數學的實踐與認識，2013，（12）：45-46.

[2] 畢義明，楊軍等.網絡圖的自動生成算法及其系統實現[J].雜技教育，2012，（1）：70-71.

[3] 付欣.網絡圖的計算機算法和顯示方法的研究[J].電腦知識與技術，2013，（3）：109-109.

作者單位

江蘇省沭陽中等專業學校 江蘇省宿遷市 223600endprint