基于HTML5的圖結構演示系統

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

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

基于HTML5的圖結構演示系統

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

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

在ASP.NET環境下，利用Javascript和XML技術實現了數據結構中的圖結構演示系統。該系統能夠讓用戶在網頁上作出無向圖、有向圖、帶權圖，能夠將所作的圖以xml文件的方式保存在服務器端以便下次使用。

數據結構；圖結構；HTML5；XML

1 系統功能

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

圖1 系統功能結構圖

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

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

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

2 圖的繪制

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

圖2 頂點類和邊類圖

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

圖3 BFS算法演示過程圖

3 圖的存儲

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

圖4 圖的存儲xml節點結構圖

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

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

4 演示算法框架

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

圖5 BFS及Kruskal算法類圖

5 結束語

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

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

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

（責任編輯：吳湘銀）

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