1. 研究目的与意义（文献综述）

研究背景及意义

图是由顶点和连接顶点的边构成的离散结构，也是计算机科学中最常用的一类抽象数据结构。图在结构和语义方面比线性表和树更加复杂，更具有一般性表示能力。几乎可以想到的每种学科中的问题都可以运用图模型来求解。传统应用如运输路线的规划、 通信网络的分析 、 科技文献的引用分析等 ； 新兴应用如蛋白质相互作用分析、电子电路设计、社交网络分析 ^[1-3]等。随着信息技术的飞速发展，人类社会的信息化程度也不断提高。大量不同个体之间彼此交互产生的数据以图的形式表现，在通信、互联网、电子商务、社交网络和物联网等领域中积累了大量的图数据。图数据规模巨大并且不断增长。据ＣＮＮＩＣ 统计 ， ２０１０ 年中国网页规模达到６００ 亿 ， 年增长率 ７８．６％。主流搜索引擎已经部署好架构，可以支持 1 万亿个顶点的 web 图的搜索处理^[4]。图数据处理的应用范围不断拓展，也变得日趋重要。

图的应用和处理技术正在快速发展，图的理论也愈发完善。

2. 研究的基本内容与方案

基本内容与目标

1）通过阅读相关文献，理解广度优先搜索（bfs, breadth first search） ^[5] 和深度优先搜索（dfs, depth first search） ^[6] ，单源最短路径问题（sssp, single sourceshortest paths）^[7] ，全源最短路径问题（all-pairs shortest paths problem）连通分量（cc,connected components） ^[8] 问题，pagerank算法的内容，应用范围，算法实现等

2）学习python语言，学习linux操作系统平台。

3. 研究计划与安排

(1)2018/1/14—2018/3/5：确定选题，查阅文献，外文翻译和撰写开题报告；

(2)2018/3/6—2018/4/30：系统架构、程序设计与开发、系统测试与完善；

(3)2018/5/1—2018/5/25：撰写及修改毕业论文；

4. 参考文献（12篇以上）

[1] berman h m, westbrook j, feng z, et al.the protein data bank. nucleic acids

research, 2000, 28(1): 235-242

[2] ogata h, goto s, sato k, et al. kegg:kyoto encyclopedia of genes and genomes.