網(wǎng)絡(luò)圖的計算機(jī)算法和顯示方法探究

於政理

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

關(guān)鍵詞：圖網(wǎng)絡(luò)；計算機(jī)算法；顯示方法；控制算法

中圖分類號：TP319 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-2064（2018）20-0015-02

網(wǎng)絡(luò)圖可將日?？梢姷母鞣N原始網(wǎng)絡(luò)圖中機(jī)構(gòu)和原件抽象出來，形成計算機(jī)可識別的拓?fù)浣Y(jié)構(gòu)。利用網(wǎng)絡(luò)圖，工作人員可對原始網(wǎng)路進(jìn)行定量或定性分析，并在此基礎(chǔ)上進(jìn)行優(yōu)化處理。網(wǎng)絡(luò)圖發(fā)揮的作用已經(jīng)得到了普遍認(rèn)可，在學(xué)術(shù)領(lǐng)域，網(wǎng)絡(luò)圖的計算機(jī)算法和顯示方法已經(jīng)成為較為熱門的研究領(lǐng)域[1]。因此，開展網(wǎng)絡(luò)圖的計算機(jī)算法和顯示方法研究具有重要的使用價值和研究意義。

1 網(wǎng)絡(luò)圖的概念及相關(guān)理論

網(wǎng)絡(luò)圖是指將實際原始網(wǎng)絡(luò)的結(jié)構(gòu)和各類原件的相關(guān)網(wǎng)絡(luò)信息，如網(wǎng)絡(luò)的結(jié)構(gòu)、元件的種類、各種參量等，抽象成計算機(jī)能夠接收和理解的拓?fù)浣Y(jié)構(gòu)[2]。

關(guān)于網(wǎng)絡(luò)圖的研究主要包括網(wǎng)絡(luò)圖的計算算法和網(wǎng)絡(luò)圖的顯示算法兩個方面。在網(wǎng)絡(luò)圖的計算算法方面，目前的研究主要集中在點符號全控制算法和邊符號控制算法兩類。網(wǎng)絡(luò)圖的顯示方法和相關(guān)算法以計算機(jī)相關(guān)顯示理論為基礎(chǔ)，對網(wǎng)絡(luò)圖進(jìn)行繪制，且繪制出的網(wǎng)絡(luò)圖可進(jìn)行大小和位置的更改。

2 網(wǎng)絡(luò)圖的計算算法

2.1 點符號全控制算法

點符號控制算法將點符號的相關(guān)基礎(chǔ)理論與全控制算法相結(jié)合。點符號全控制算法在融合了符號控制算法的基礎(chǔ)上，又引入了限定了最大度和最小度的極限度的概念。點符號控制算法關(guān)注的是局部占優(yōu)問題，點符號全控制算法是對點符號控制算法的改進(jìn)和延伸，能夠?qū)⒃瓉矸柨刂扑惴ㄖ?，部分處于閉領(lǐng)域中點擴(kuò)展到開領(lǐng)域，從不同的角度開展研究，同時，通過引入最大度和最小度，可為一般的網(wǎng)絡(luò)圖中給出下限。在隨后的研究過程中，研究人員提出了更多新的網(wǎng)絡(luò)圖符號控制邊界，提高了原有邊界的適用性。隨著符號全控制算法的不斷充實和完善，反符號算法也被研究者們提出，這種反符號算法為符號全控制算法提出了新的研究思路和研究視角，為算法的后續(xù)研究提供了更為堅實的基礎(chǔ)，可進(jìn)一步提高網(wǎng)絡(luò)圖的計算速度[3]。

2.2 邊符號控制算法

邊符號控制算法的相關(guān)概念由徐保于2001年提出，邊符號控制算法的提出，對網(wǎng)絡(luò)圖控制算法的內(nèi)容進(jìn)行了充實和完善。隨后，有學(xué)者對邊符號控制算法進(jìn)行了發(fā)展和完善，對邊符號控制算法的上下界和算法數(shù)給出了較為準(zhǔn)確的具體數(shù)值，對界限進(jìn)行了完善。邊符號控制算法是對符號邊算法的隱身。在最近的關(guān)于邊符號控制算法的研究中，研究者們將原有邊符號控制算法中的函數(shù)值域卜由[-1，1]改成[-1，0，1]，提出了成為減邊控制的算法，但是由于減邊控制算法的相關(guān)研究難度較大，目前尚未出現(xiàn)有代表性的研究成果，關(guān)于減邊控制算法的研究仍在繼續(xù)。

點符號控制算法和邊符號控制算法的提出和完善初步構(gòu)成了可顯示和查詢點的網(wǎng)絡(luò)圖系統(tǒng)，但是，這種系統(tǒng)尚不夠完善，無法對操作的歷史記錄進(jìn)行查看，且顯示的圖像不夠清晰，為了完善該系統(tǒng)，可通過發(fā)揮數(shù)據(jù)庫的作用來改進(jìn)，實現(xiàn)對數(shù)據(jù)的快速查詢。

3 網(wǎng)絡(luò)圖的顯示方法

3.1 基礎(chǔ)理論

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

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

對繪制出的網(wǎng)絡(luò)圖，有時需要根據(jù)需求調(diào)整圖形的位置、大小等屬性，因此，圖形需具備平移、縮放和旋轉(zhuǎn)等功能。

3.2 顯示步驟

完成網(wǎng)絡(luò)圖的顯示算法，通常包括以下幾個步驟：

步驟1：圖形繪制。研究人員根據(jù)用戶輸入的網(wǎng)絡(luò)圖信息，在計算機(jī)屏幕上將網(wǎng)絡(luò)圖的完整圖形繪制出來；

步驟2：邊描繪。對步驟1得到的圖形，對新添加的邊，根據(jù)邊的信息不同，分別用不同的顏色對邊進(jìn)行標(biāo)注；

步驟3：連通圖構(gòu)建。根據(jù)用戶新添加的點和邊的信息，將圖形中的點相互連接，構(gòu)成連通圖，同時用不同的顏色對新添加的點和邊進(jìn)行標(biāo)注；

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

步驟5：點刪除。在繪制圖形時，需要刪除多余的點，在刪除點時，應(yīng)當(dāng)同時刪除與該點相關(guān)聯(lián)的邊；

步驟6：記錄操作。為了便于后期的操作查詢，在對網(wǎng)絡(luò)圖的各種操作都應(yīng)當(dāng)詳細(xì)準(zhǔn)確記錄；

步驟7：觀測時間。在每次操作網(wǎng)絡(luò)圖時，準(zhǔn)確記錄操作時間；

步驟8：構(gòu)建系統(tǒng)。構(gòu)建網(wǎng)絡(luò)圖的顯示和查詢系統(tǒng)，該系統(tǒng)對外提供顯示和查詢功能，可查詢網(wǎng)絡(luò)圖的連通性和最短路徑。

3.3 顯示問題

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

4 網(wǎng)絡(luò)圖的計算機(jī)算法和顯示方法的改進(jìn)

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

4.1 層次策略

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

4.2 搜索策略

搜索的盲目性使得傳統(tǒng)的最短路徑算法效率較低，遍歷了大量無用節(jié)點。在搜索策略上的改進(jìn)，可對原有算法進(jìn)行啟發(fā)式引導(dǎo)，加快算法的執(zhí)行進(jìn)度?，F(xiàn)有的搜索策略改進(jìn)方法大多包括層次策略、貪心策略和方向策略。搜索策略選擇的是否正確直接影響著算法的計算效率和精度。通過對搜索策略的優(yōu)化，可使得傳統(tǒng)最短路徑算法具有更快的響應(yīng)速度和計算精度，以及較低的內(nèi)存消耗。

4.3 堆運(yùn)算

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

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

5 結(jié)語

網(wǎng)絡(luò)圖的發(fā)展和計算機(jī)技術(shù)的發(fā)展，促進(jìn)了兩者的結(jié)合和應(yīng)用，未來將能夠在更多領(lǐng)域發(fā)揮重要作用，因此，網(wǎng)絡(luò)圖的控制算法理論具有廣闊的應(yīng)用前景和實用價值。但是，該領(lǐng)域仍有很多問題需要進(jìn)一步研究，網(wǎng)絡(luò)圖的控制算法理論仍需要進(jìn)一步完善。

參考文獻(xiàn)

[1]劉曉飛.探究網(wǎng)絡(luò)圖的計算機(jī)算法和顯示方法[J].安慶師范大學(xué)學(xué)報（自然科學(xué)版），2016，22（2）：86-88.

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

[3]宋碧慧.網(wǎng)絡(luò)圖的計算機(jī)算法及顯示方法研究[J].無線互聯(lián)科技，2017，（21）：48-49.

[4]韓正一.基于網(wǎng)絡(luò)圖的計算機(jī)算法研究[J].信息通信，2016，（3）：43-44.