摘 要：图是一种重要的数据结构，被广泛用于复杂的数据建模。本文研究了各种算法的存储方式及实现方法和原理。对现有的算法进行深入的阐述和比较，得出其优劣性以方便不同方式的遍历查询。子图查询是图在工程应用中的一个突出问题。本文利用节点与边的关系，求解最短距离与最优造价。同时应用图中的关系求解最优编辑路径的方法，经试验证明与算法分析研究，此方法可以有效地计算图中的编辑距离。36374
毕业论文关键词：图结构；算法；存储方式
The Function and Research of Algorithms Based on Graph
Abstract: Graph is important data structures which are widely used for complex data modeling. This paper researches the various algorithms and the theory, implementation of storage methods.Deeply expounding and comparing the existing algorithms is the basis of different ways of traversing query. Sub-graph query is a prominent problem in engineering application. This paper uses in the relationship between optimal edit path. At the same time the relationship between the application diagram editors for solving the optimal path method, the test proved that the analysis of algorithms, this method can compute the edit distance graph.
Key words: Graph Structure; algorithms; storage methods
 目    录
摘 要    1
引言    1
1. 研究背景及工作    2
1.1 研究背景    2
1.2 图的重要性    2
1.3 论文的主要工作    3
2. 图的相关概念与表示方法    3
2.1 相关概念    3
2.2 图的存储结构    3
2.2.1邻接矩阵    3
2.2.2邻接表    4
3.图的经典算法    4
3.1 现有图算法及应用    4
3.2 图的压缩存储    5
3.3图的算法    5
3.3.1 Prim算法    5
3.3.2 KrusKual算法    6
3.3.3 Dijkstra算法    6
3.4 实验结果与分析    8
4.总结与展望    8
参考文献    9
致谢    10
基于图的算法性能研究  引言
上世纪90年代早期，大部分数据发掘来自数据库方面，主要是对数据进行剖析。但是这已远远不能满足当今的互联网大数据时代，由于数据的半结构化和非结构化，常用的关系数据库显得力不从心，越来越多的现实问题摆在我们面前，同时也提出了更高的要求。因此，用图来表述这些非结构化的数据成为新的研究方法，主要原因是图可以用来建模并且表示多种具有复杂结构化的数据，同时也给数据的描述带来很多方便，因此在大数据时代得到了广泛的应用。
1. 研究背景及工作
1.1 研究背景
    随着计算机科学与信息技术的拓展，数据的应用越来越广泛，计算机已经深入到人类社会的各个领域。计算机的应用不仅仅局限在科学计算，更多应用于非数值数据的处理[1]。比如处理表格、字符、图像等各种具备不同结构的数据，这类数据给程序设计带来了新的问题。人们开始用节点来表示一个关系集或一个独立的事物。在图中，顶点对应对象中的实体，边对应顶点之间的关系[8]。因此采用什么类型的结构来存储不同事物及这些事物之间的关系，如何设计低存储与高效率的算法显得尤为重要，而基于图的数据结构更有利于处理上述问题。
    近年来，图的运用引起了计算机领域的密切关注，主要原因在于大量数据存在，人们急需要将其大量的数据转化为有用的信息。比如电子商务的广泛普及、软件工程、市场研究、城市交通里程图等领域。针对于图的不同应用场合，使得对图的算法性能研究具有了更深刻的意义。 基于图的算法性能研究+源代码:http://www.youerw.com/jisuanji/lunwen_34784.html