图论算法 文献综述

《图论算法 文献综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、阳光学院计算机工程系2011届毕业设计文献综述题目：图论算法中图画法生成平台设计年级：2007学号：240792261姓名：洪惠貌指导教师：2011年01月17日前言:在一般的应用程序中，要处理图的信息，先要输入图的信息，而输入图的信息，主要是输入图的顶点，及与顶点所关联的边的信息。在图的顶点以及变数相当多的情况下，是相当麻烦的一种事情，而且也容易出错。为了解决这问题，本课题着重研究图论中图画法生成平台。本平台设计描述了通过这一平台，用户只要用鼠标轻松地点击就能画出图的点，以及它们所关联的边的信息。并在此基础上，立即生成相应图的邻接矩阵或邻接表。以此来代替图信息的输入、输出

2、。正文：图论算法中图画法生成平台是一种值得研究的画图平台，此平台主要能为用户提供画有向图、无向图、带权图，以及能算出这三种图所对应的邻接矩阵或邻接表，同时具备图的编辑，图的存盘，图的打开及重现。图是由两个集合V和VR组成的，其中V是顶点的有穷非空集合，VR是定义在顶点集合上的一个关系。图也包括有向图和无向图，其中有向图是顶点和弧组成的图，无向图是顶点和边组成的图。由于图的结构比较复杂，任意两个顶点之间都可能存在关系，无法以顶点在存储区中的物理位置来表示元素之间的关系，因此很难使用顺序存储结构来存放图。如果使用多重链表表示图，即由一个数据域和多个指针域组成的节点表示图中的一个

3、顶点，顶点之间的边或弧用指针关联起来，这是一种最简便的链式存储结构，但是由于图中各顶点的度各不相同，这样节点的指针域不定长，给算法的设计带来很大的困难。在实际应用中，应该根据具体的图来设计适当的存储结构。常用的图的存储结构有：邻接矩阵表示法、邻接表表示法、十字链表表示法和多重链表表示法。本平台设计只要包括邻接矩阵表示法、邻接表表示法。其中邻接矩阵是图的一种顺序存储结构，有两个数组分别表示存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。而邻接表是图的一种链式存储结构，它包括表结点和头结点，表结点是指在邻接表中，对图中的每一个顶点建立一个单链表，第i个单链表中的

4、结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧），每个表结点由邻接点域、链域、数据域等三个域组成。头结点是在邻接表中，每个单链表上附设一个结点，每个结点由链域和数据域两个域组成。如果无向图中有n个顶点、e条边，则它的邻接表需要n个头结点和2e个表结点。显然，在边稀疏的情况下，用邻接表表示图比邻接矩阵节省存储空间。总结：图论算法中图画法生成平台为用户提供画有向图、无向图、带权图，以及能算出这三种图所对应的邻接矩阵或邻接表，同时具备图的编辑，图的存盘，图的打开及重现。此平台给图论算法的计算机实现带来可视化的效果。无论在大学《离散数学》、《数据结构教程》的教学，还是在实

5、际应用中都有现实意义。参考文献[1]常建功.C#3.0完全自学手册.北京：机械工业出版社，2009,1.[2]周亚玲，苏治中.Delphi开发实用编程200例.北京：中国铁道出版社,2005,10.[3]彭波.数据结构教程.北京：清华大学出版社,2004,3.[4]微软公司,东方人华.《C#编程技术》-北京：清华大学出版社;2001[5]李刚.Struts2.1权威指南——基于WebWork核心的MVC开发[M].北京：电子工业出版社，2009,5.[6]李刚.整合STRUTS+HIBERNATE+SPRING应用开发详解[M].北京：电子工业出版社,2007,1.[7]李

6、刚.轻量级JavaEE企业应用实战——Struts2＋Spring＋Hibernate整合开发[M].北京：电子工业出版社,2008,11.[8]夏昕，曹晓钢，唐勇.深入浅出Hibernate[M].北京：电子工业出版社,2005,6.[9]（美）鲍格斯坦（Bergsten，H.）著,林琪，朱涛江译.JSP设计（第三版）/O’ReillyJava系列[M].北京：中国电力出版社,2004,12.[10]马骏,C#网络应用编程，人民邮电出版社,2010,4.