網絡圖的計算機算法和顯示方法探究

於政理

摘 要：隨著信息技術的不斷發展，網絡圖在很多領域發揮了越來越重要的作用，關于網絡圖的計算機算法和顯示方法的研究受到了研究者們的廣泛關注。本文首先介紹了網絡圖的相關概念和理論；其次，闡述了網絡圖的計算算法，包括點符號全控制算法和邊符號控制算法；然后從基礎理論、步驟和需要注意的問題等三個方面詳細介紹了網絡圖的顯示方法；最后，提出了網絡圖的計算機算法和顯示方法的改進策略，包括層次策略、搜索策略和堆運算等。

關鍵詞：圖網絡；計算機算法；顯示方法；控制算法

中圖分類號：TP319 文獻標識碼：A 文章編號：1671-2064（2018）20-0015-02

網絡圖可將日常可見的各種原始網絡圖中機構和原件抽象出來，形成計算機可識別的拓撲結構。利用網絡圖，工作人員可對原始網路進行定量或定性分析，并在此基礎上進行優化處理。網絡圖發揮的作用已經得到了普遍認可，在學術領域，網絡圖的計算機算法和顯示方法已經成為較為熱門的研究領域[1]。因此，開展網絡圖的計算機算法和顯示方法研究具有重要的使用價值和研究意義。

1 網絡圖的概念及相關理論

網絡圖是指將實際原始網絡的結構和各類原件的相關網絡信息，如網絡的結構、元件的種類、各種參量等，抽象成計算機能夠接收和理解的拓撲結構[2]。

關于網絡圖的研究主要包括網絡圖的計算算法和網絡圖的顯示算法兩個方面。在網絡圖的計算算法方面，目前的研究主要集中在點符號全控制算法和邊符號控制算法兩類。網絡圖的顯示方法和相關算法以計算機相關顯示理論為基礎，對網絡圖進行繪制，且繪制出的網絡圖可進行大小和位置的更改。

2 網絡圖的計算算法

2.1 點符號全控制算法

點符號控制算法將點符號的相關基礎理論與全控制算法相結合。點符號全控制算法在融合了符號控制算法的基礎上，又引入了限定了最大度和最小度的極限度的概念。點符號控制算法關注的是局部占優問題，點符號全控制算法是對點符號控制算法的改進和延伸，能夠將原來符號控制算法中，部分處于閉領域中點擴展到開領域，從不同的角度開展研究，同時，通過引入最大度和最小度，可為一般的網絡圖中給出下限。在隨后的研究過程中，研究人員提出了更多新的網絡圖符號控制邊界，提高了原有邊界的適用性。隨著符號全控制算法的不斷充實和完善，反符號算法也被研究者們提出，這種反符號算法為符號全控制算法提出了新的研究思路和研究視角，為算法的后續研究提供了更為堅實的基礎，可進一步提高網絡圖的計算速度[3]。

2.2 邊符號控制算法

邊符號控制算法的相關概念由徐保于2001年提出，邊符號控制算法的提出，對網絡圖控制算法的內容進行了充實和完善。隨后，有學者對邊符號控制算法進行了發展和完善，對邊符號控制算法的上下界和算法數給出了較為準確的具體數值，對界限進行了完善。邊符號控制算法是對符號邊算法的隱身。在最近的關于邊符號控制算法的研究中，研究者們將原有邊符號控制算法中的函數值域卜由[-1，1]改成[-1，0，1]，提出了成為減邊控制的算法，但是由于減邊控制算法的相關研究難度較大，目前尚未出現有代表性的研究成果，關于減邊控制算法的研究仍在繼續。

點符號控制算法和邊符號控制算法的提出和完善初步構成了可顯示和查詢點的網絡圖系統，但是，這種系統尚不夠完善，無法對操作的歷史記錄進行查看，且顯示的圖像不夠清晰，為了完善該系統，可通過發揮數據庫的作用來改進，實現對數據的快速查詢。

3 網絡圖的顯示方法

3.1 基礎理論

利用計算機來顯示網絡圖往往利用較為基礎的C語言實現。利用C語言顯示網絡圖的優勢在于，一方面C語言本身功能強大，且該語言相對簡潔，十分適合在屏幕上實現對網絡圖的回執，另一方面，C語言具有較高的執行率，在運行C語言程序時，程序占用系統的內存相對較少且運行速度比其他語言更快[4]。在對網絡圖進行分析時，通常從點和連線兩方面入手，盡管這種分析方法具有一定效果，但是由于點和邊的關系有時較為復雜，不可避免出現錯誤。針對該問題，研究人員通常利用C語言，首先繪制出各個頂點，然后在頂點之間建立連接，實現時利用物理坐標，坐標形式如圖1所示。

如圖1所示，在所用的物理坐標系中，垂直方向為縱軸（即Y軸），且向下為正；水平向下為橫軸（即X軸），且向右為正。在使用該物理坐標系時，要求點的坐標必須為在某一范圍內的整數。

對繪制出的網絡圖，有時需要根據需求調整圖形的位置、大小等屬性，因此，圖形需具備平移、縮放和旋轉等功能。

3.2 顯示步驟

完成網絡圖的顯示算法，通常包括以下幾個步驟：

步驟1：圖形繪制。研究人員根據用戶輸入的網絡圖信息，在計算機屏幕上將網絡圖的完整圖形繪制出來；

步驟2：邊描繪。對步驟1得到的圖形，對新添加的邊，根據邊的信息不同，分別用不同的顏色對邊進行標注；

步驟3：連通圖構建。根據用戶新添加的點和邊的信息，將圖形中的點相互連接，構成連通圖，同時用不同的顏色對新添加的點和邊進行標注；

步驟4：邊刪除。在繪制指定的圖形時，需要刪除圖中多余的邊，在刪除邊時應當保證圖中所有點不能成為孤立的點，必須至少要和一個點有連接關系；

步驟5：點刪除。在繪制圖形時，需要刪除多余的點，在刪除點時，應當同時刪除與該點相關聯的邊；

步驟6：記錄操作。為了便于后期的操作查詢，在對網絡圖的各種操作都應當詳細準確記錄；

步驟7：觀測時間。在每次操作網絡圖時，準確記錄操作時間；

步驟8：構建系統。構建網絡圖的顯示和查詢系統，該系統對外提供顯示和查詢功能，可查詢網絡圖的連通性和最短路徑。

3.3 顯示問題

在繪制網絡圖時，除了遵循上述步驟，還需注意相關的細節問題。網絡圖的顯示是在點符號全控制算法和邊控制算法的基礎上進行的。研究人員在向系統中輸入繪制的數據時，通常需要首先輸入繪圖的指令，然后在輸入網絡圖的點的個數和編號、邊的數量和編號，以及點的坐標等信息，最后將數據加入到創建的鄰接多重表（鄰接表的結構如圖2所示），這些步驟涉及很多細節性的問題需要注意。例如，在輸入邊和點的信息時，需要首先輸入相關質量，然后在向其中數據點或邊的數量、起點和終點的熟練阿根、編號等，有時需要修改鄰接多重表后才能完成整個網絡圖的繪制工作。在添加新的點時，如果該點具有孤立性且網絡連通性不完整時，需要對網絡圖進行基本控制。

4 網絡圖的計算機算法和顯示方法的改進

最短路徑問題時圖論中的經典問題之一，隨著信息技術的不斷發展，網絡變得更為復雜，最短路徑問題的研究更注重于時效性。本文從層次策略、搜索策略和堆運算三個方面詳細闡述網絡圖的計算機算法和顯示方法的改進策略。

4.1 層次策略

將問題的規模進行降階是降低算法復雜度的有效方法之一。為了降低最短路徑算法的復雜度，可采用層次策略，將網絡中的主要節點和相關的邊提取出來，構建成具有層次化的結構模型，將網絡的結構進行簡化，使得網絡結構中每個層次僅為其上一個層次的子集。層次策略中，分層的等級越高則涉及的邊和節點越少。在分層的網絡圖中執行最短路徑計算時，首先在原來網絡的初始點及其局部開始，然后進入更高層次，在靠近目標點時回到原網絡，直至到達目標。這樣可有效減少需要遍歷的節點數，提高算法效率。

4.2 搜索策略

搜索的盲目性使得傳統的最短路徑算法效率較低，遍歷了大量無用節點。在搜索策略上的改進，可對原有算法進行啟發式引導，加快算法的執行進度。現有的搜索策略改進方法大多包括層次策略、貪心策略和方向策略。搜索策略選擇的是否正確直接影響著算法的計算效率和精度。通過對搜索策略的優化，可使得傳統最短路徑算法具有更快的響應速度和計算精度，以及較低的內存消耗。

4.3 堆運算

對算法執行中數據結構進行優化也是提高算法執行效率的有效方式之一，可采用的常見的數據結構有桶結構和堆結構，本文重點關注堆結構。堆結構中較為普遍使用的是二叉堆、二項堆和Fibonacci堆。在堆運算中，需要對堆進行修復和維護，以保證其一直具有堆序的原有特性，涉及到的運算主要包括：（1）刪除最小值：在刪除最小值時，首先用堆中最后元素替換根節點，降低堆的大小，然后將改點下濾，最后刪除，以免影響堆的特性；（2）插入：需要先將堆大小加1，然后將需要插入的松弛節點加到堆的末尾，最后上濾到滿足堆性質；（3）修改鍵值：當數據結構遭到調整，堆的特性受到影響時，需要采用上濾的方式進行修復。

采用二叉堆運算對算法僅優化時，整個算法的時間復雜度僅為O（mlogn），顯著提高了原有算法的性能。

5 結語

網絡圖的發展和計算機技術的發展，促進了兩者的結合和應用，未來將能夠在更多領域發揮重要作用，因此，網絡圖的控制算法理論具有廣闊的應用前景和實用價值。但是，該領域仍有很多問題需要進一步研究，網絡圖的控制算法理論仍需要進一步完善。

參考文獻

[1]劉曉飛.探究網絡圖的計算機算法和顯示方法[J].安慶師范大學學報（自然科學版），2016，22（2）：86-88.

[2]齊安智.控制算法理論及網絡圖計算機算法顯示研究[J].中國新通信，2018，（1）：101.

[3]宋碧慧.網絡圖的計算機算法及顯示方法研究[J].無線互聯科技，2017，（21）：48-49.

[4]韓正一.基于網絡圖的計算機算法研究[J].信息通信，2016，（3）：43-44.