基于HTML5的圖結(jié)構(gòu)演示系統(tǒng)

陳俊建，蔣偉杰，羅 康，何 勇

（陽(yáng)光學(xué)院，福建 福州 350000）

基于HTML5的圖結(jié)構(gòu)演示系統(tǒng)

陳俊建，蔣偉杰，羅 康，何 勇

（陽(yáng)光學(xué)院，福建 福州 350000）

在ASP.NET環(huán)境下，利用Javascript和XML技術(shù)實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的圖結(jié)構(gòu)演示系統(tǒng)。該系統(tǒng)能夠讓用戶在網(wǎng)頁(yè)上作出無(wú)向圖、有向圖、帶權(quán)圖，能夠?qū)⑺鞯膱D以xml文件的方式保存在服務(wù)器端以便下次使用。

數(shù)據(jù)結(jié)構(gòu)；圖結(jié)構(gòu)；HTML5；XML

1 系統(tǒng)功能

基于HTML5的圖結(jié)構(gòu)演示系統(tǒng)的主要功能分為三大部分，即頁(yè)面前端圖的繪制、針對(duì)xml文件中所存儲(chǔ)圖的管理以及基于圖結(jié)構(gòu)的常見算法演示[1]，系統(tǒng)的功能結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)功能結(jié)構(gòu)圖

圖的繪制功能模塊實(shí)現(xiàn)在頁(yè)面上繪圖功能，繪制圖的過(guò)程主要由以下幾個(gè)步驟構(gòu)成：（1）設(shè)置所繪制圖的類型，即無(wú)向圖或有向圖，帶權(quán)圖或不帶權(quán)圖。（2）繪制頂點(diǎn)，設(shè)置頂點(diǎn)的名稱。（3）根據(jù)頂點(diǎn)繪制邊，若是帶權(quán)圖則繼續(xù)設(shè)置邊上的權(quán)值。（4）若所繪制的圖存在問(wèn)題，則可以使用更改頂點(diǎn)名稱、邊權(quán)值、刪除頂點(diǎn)或邊等功能繼續(xù)完善所要繪制的圖。（5）為繪制好的圖命名并保存添加至服務(wù)器端xml文件。

圖的管理功能模塊能夠管理服務(wù)器端xml文件所存儲(chǔ)的圖，可以將服務(wù)器端所存儲(chǔ)的圖重新進(jìn)行重命名、編輯圖的頂點(diǎn)、邊以及權(quán)值等信息或?qū)D從服務(wù)器端直接刪除。

算法演示功能模塊實(shí)現(xiàn)了在指定的圖上演示相應(yīng)的算法，在演示過(guò)程中算法采用單步執(zhí)行，執(zhí)行算法過(guò)程中所產(chǎn)生的結(jié)果使用動(dòng)畫進(jìn)行展示，動(dòng)畫效果主要含頂點(diǎn)的顏色變化、頂點(diǎn)的閃爍、邊的顏色及寬度變化、邊的增長(zhǎng)等。在演示過(guò)程中，還能夠輸出算法執(zhí)行過(guò)程中所使用的數(shù)據(jù)結(jié)構(gòu)內(nèi)的數(shù)據(jù)變化。

2 圖的繪制

在網(wǎng)頁(yè)上繪圖是由HTML5中的canva標(biāo)簽為容器，使用Javascript腳本語(yǔ)言控制，采用面向?qū)ο蟮脑O(shè)計(jì)思想來(lái)實(shí)現(xiàn)的。頁(yè)面上的圖信息由兩個(gè)對(duì)象集合vers和edges來(lái)維護(hù)，vers是頂點(diǎn)對(duì)象的集合，edges是邊對(duì)象的集合，頁(yè)面上的圖信息發(fā)生任何改變都將引起vers與edges內(nèi)對(duì)象屬性的改變，因此在canvas中繪圖時(shí)只需根據(jù)vers及edges內(nèi)的對(duì)象進(jìn)行重繪即可。算法演示過(guò)程中動(dòng)畫的實(shí)現(xiàn)也是不斷改變對(duì)象的屬性并在canvas上重繪的過(guò)程。頂點(diǎn)對(duì)象屬于頂點(diǎn)類vertex，包含了頂點(diǎn)的位置、名稱、邊框?qū)挾?、邊框顏色、填充色、透明度等屬性，以及頂點(diǎn)的繪制和狀態(tài)設(shè)置兩個(gè)方法；邊對(duì)象屬于邊類edge，包含了邊起點(diǎn)、邊終點(diǎn)、邊權(quán)值、邊寬度、邊框顏色、透明度等屬性，以及邊的繪制和狀態(tài)設(shè)置兩個(gè)方法；兩個(gè)類的類圖如圖2所示。

圖2 頂點(diǎn)類和邊類圖

以BFS演示算法為例，其演示過(guò)程中的的效果如圖3所示。

圖3 BFS算法演示過(guò)程圖

3 圖的存儲(chǔ)

為實(shí)現(xiàn)系統(tǒng)的快速移植和部署，系統(tǒng)采用了輕量化的存儲(chǔ)方式，使用xml格式來(lái)存儲(chǔ)系統(tǒng)上所繪制的圖，其xml樹結(jié)構(gòu)如圖4所示：橢圓代表節(jié)點(diǎn)，方框內(nèi)為節(jié)點(diǎn)的屬性。

圖4 圖的存儲(chǔ)xml節(jié)點(diǎn)結(jié)構(gòu)圖

其中Graphs為根節(jié)點(diǎn)，其下可含多個(gè)Graph子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)分別表示一個(gè)圖，Graph節(jié)點(diǎn)具有圖名、是否是有向圖、是否帶權(quán)等屬性。Graph有兩個(gè)子節(jié)點(diǎn)vertexs和edges，代表頂點(diǎn)集和邊集，vertexs節(jié)點(diǎn)具有數(shù)量屬性，與子節(jié)點(diǎn)v的數(shù)量相對(duì)應(yīng)，每個(gè)v節(jié)點(diǎn)代表一個(gè)頂點(diǎn)，具有位置和頂點(diǎn)名稱屬性；edges節(jié)點(diǎn)具有數(shù)量屬性，與子節(jié)點(diǎn)eg的數(shù)量相對(duì)應(yīng)，每個(gè)eg節(jié)點(diǎn)代表一條邊，具有邊的端點(diǎn)名稱和權(quán)值屬性。

為了便于保存和使用，存儲(chǔ)圖的xml文件保存在服務(wù)器端，保存所繪制的圖時(shí)為了服務(wù)器的安全使用服務(wù)器端語(yǔ)言C#構(gòu)建xml結(jié)點(diǎn)并存入xml文件；圖的載入使用javascript腳本從xml中讀取并解析至前端頁(yè)面。

4 演示算法框架

演示算法框架基于面向?qū)ο笏枷朐O(shè)計(jì)，包含屬性和方法兩大部分內(nèi)容，屬性內(nèi)含有算法的初始條件、算法執(zhí)行過(guò)程中需要的臨時(shí)存儲(chǔ)結(jié)構(gòu)、執(zhí)行過(guò)程中頂點(diǎn)和邊的不同狀態(tài)；方法主要有init（）和next（）兩個(gè)方法。init方法完成初始化工作，主要有建立圖的鄰接矩陣、初始化臨時(shí)存儲(chǔ)結(jié)構(gòu)、設(shè)置頂點(diǎn)和邊的初始狀態(tài)，next方法的作用是單步執(zhí)行算法，執(zhí)行時(shí)首先判斷算法的終止條件；其次根據(jù)算法修改臨時(shí)存儲(chǔ)結(jié)構(gòu)內(nèi)容、將修改內(nèi)容作為提示信息輸出到頁(yè)面；最后修改頂點(diǎn)和邊的狀態(tài)，根據(jù)不同狀態(tài)播放相應(yīng)的動(dòng)畫。在具體實(shí)現(xiàn)時(shí)，按照框架根據(jù)每一個(gè)算法的特點(diǎn)和需要構(gòu)造并生成相應(yīng)的算法對(duì)象，其后只要使用該對(duì)象就能按步驟演示算法的執(zhí)行過(guò)程。以BFS及Kruskal算法為例，如圖5所示。

圖5 BFS及Kruskal算法類圖

5 結(jié)束語(yǔ)

本系統(tǒng)利用HTML5及xml輕量存儲(chǔ)技術(shù)實(shí)現(xiàn)了基于web的圖結(jié)構(gòu)算法演示系統(tǒng)，能夠在PC端、移動(dòng)端通過(guò)瀏覽器使用，支持用戶在自定義的圖結(jié)構(gòu)上演示常用的DFS、BFS、Prim、Kruskal、Dijkstra、關(guān)鍵路徑等算法。

[1]鐘迅科.基于HTML5與CreateJS的《數(shù)據(jù)結(jié)構(gòu)與算法》演示平臺(tái)[J].現(xiàn)代計(jì)算機(jī)(專業(yè)版)，2014，2(30):61-65.

Demonstration system of graph structure based on HTML5

CHEN Jun-jian， JIANG Wei-jie， LUO Kang， HE Yong

(Sunshine college， Fuzhou Fujian 350000)

Under the environment of ASP. Net， using JavaScript and XML technology to realize the data structure graph structure demo system. The system can let users on the web made undirected graph， a directed graph， weighted graph， can be made of the map to XML files saved on the server side to the next.

Data structure; Graph structure; HTML5; XML

O723

A

10.3969/j.issn.1672-7304.2016.05.022

1672–7304(2016)05–0045–02

國(guó)家大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃（項(xiàng)目編號(hào)：201513468004）；福建省2015年度大學(xué)生創(chuàng)新創(chuàng)業(yè)計(jì)劃訓(xùn)練項(xiàng)目“基于HTML5的圖論演示系統(tǒng)”（項(xiàng)目編號(hào)：201513468004）。

（責(zé)任編輯：吳湘銀）

陳俊建（1994-），男，福建福州人，研究方向：智能計(jì)算、圖像處理。