於政理

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

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

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

網(wǎng)絡(luò)圖可將日?？梢姷母鞣N原始網(wǎng)絡(luò)圖中機(jī)構(gòu)和原件抽象出來，形成計(jì)算機(jī)可識(shí)別的拓?fù)浣Y(jié)構(gòu)。利用網(wǎng)絡(luò)圖，工作人員可對(duì)原始網(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ī)算法和顯示方法已經(jīng)成為較為熱門的研究領(lǐng)域[1]。因此，開展網(wǎng)絡(luò)圖的計(jì)算機(jī)算法和顯示方法研究具有重要的使用價(jià)值和研究意義。

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

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

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

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

2.1 點(diǎn)符號(hào)全控制算法

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

2.2 邊符號(hào)控制算法

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

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

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

3.1 基礎(chǔ)理論

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

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

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

3.2 顯示步驟

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

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

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

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

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

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

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

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

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

3.3 顯示問題

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

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

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

4.1 層次策略

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

4.2 搜索策略

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

4.3 堆運(yùn)算

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

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

5 結(jié)語

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

參考文獻(xiàn)

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

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

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

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