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

（陽光學院，福建 福州 350000）

基于HTML5的圖結構演示系統(tǒng)

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

（陽光學院，福建 福州 350000）

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

數(shù)據(jù)結構；圖結構；HTML5；XML

1 系統(tǒng)功能

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

圖1 系統(tǒng)功能結構圖

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

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

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

2 圖的繪制

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

圖2 頂點類和邊類圖

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

圖3 BFS算法演示過程圖

3 圖的存儲

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

圖4 圖的存儲xml節(jié)點結構圖

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

為了便于保存和使用，存儲圖的xml文件保存在服務器端，保存所繪制的圖時為了服務器的安全使用服務器端語言C#構建xml結點并存入xml文件；圖的載入使用javascript腳本從xml中讀取并解析至前端頁面。

4 演示算法框架

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

圖5 BFS及Kruskal算法類圖

5 結束語

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

[1]鐘迅科.基于HTML5與CreateJS的《數(shù)據(jù)結構與算法》演示平臺[J].現(xiàn)代計算機(專業(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

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

（責任編輯：吳湘銀）

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