基于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-），男，福建福州人，研究方向：智能计算、图像处理。