毕业论文
计算机论文
经济论文
生物论文
数学论文
物理论文
机械论文
新闻传播论文
音乐舞蹈论文
法学论文
文学论文
材料科学
英语论文
日语论文
化学论文
自动化
管理论文
艺术论文
会计论文
土木工程
电子通信
食品科学
教学论文
医学论文
体育论文
论文下载
研究现状
任务书
开题报告
外文文献翻译
文献综述
范文
基于图的算法性能研究+源代码(2)
1.2 图的重要性
图在计算机科学领域中是常用的一类数据结构,它被广泛用于复杂的数据建模。譬如在城市连接图中,图中的权值表示表示两个城市之间的距离(单位为1000KM),要计算一条铁路或公路连接所有城市(即从任意一个城市出发都可以到达另外一个目的城市)设计一种算法,求出最小代价。在描述此问题时,通常以图中的顶点来代替城市,图中的边表示道路,用图中的顶点数V和边数E来度量输入的规模,用权值表示代价。在交际网中,全部社会关系也能够概括为一个图,点代表社会中的个体,边代表个体之间的关系,社交网中的社区就能够表示为一个子图,挖掘社会关系
网络
中具有某些特征的社区具有非常重要的现实意义。
最新的应用例如
生物
分子、互联网络、物流流通工程开发等提出了对图应用的更高要求。对于图的算法性能研究已经成为一个重要的研究课题,很多在科学与工程方面已有大批量可用的数据,如化合物的分子结构、校园局域网。随着时间的推移,所积累的图数据越来越多,大量数据的存在也给图的查询带来极大的困难[3]。作为现实应用中的问题之一,图的算法性能研究也成为相关研究的热点。
1.3 论文的主要工作
目前对于图的研究已经取得了多方面的成果,基于图的算法被应用到许多领域,如物流、网络、城市交通里程图。本论文的主要工作包含如下几个方面:
(1)图的邻接表和邻接矩阵两种不同存储方式;
(2)采用狄杰斯特拉算法、普利姆算法和克鲁斯卡尔算法实现最小生成 树的查找;
(3)对比上述三种算法的性能及优缺点。
2. 图的相关概念与表示方法
本章将对关于图的一些术语进行描述,包含图的存放表示法、图的遍历查询方法和三个经典算法。
2.1 相关概念
图:它是由节点和边两个集合V和E组成的,将其记为G=(V,E),其中E是V中顶点的偶对的有限集合,V是节点的有限非空集合,这些节点偶对成为边。在一个图要么为有向图,要么为无向图。不会存在部分无向图部分为有向图的情况。
子图:假设有两个这样的图g1=(v1,e1)和G=(V,E),如果g1是G的一个子集,即是g1属于G,且e1是E的一个子集,即是e1属于E,且v1是V的一个子集,即是v1属于V,如果满足上述条件,我们就称g1属于G的子图[3]。
2.2 图的存储结构
2.2.1邻接矩阵
邻接矩阵是表示节点之间邻接关系的一种矩阵表示形式。
假定G=(V,E)是N个节点的无向图,则G的邻接矩阵不妨有如下定义的N阶方阵:
A[i][j]=1:代表i和j之间有边(i,j)
A[i][j]=0:代表i和j之间没有边(i,j)
A[i][j]=0:代表顶点i到自身没有边。
2.2.2邻接表
邻接表是图的一种链式存储结构,它用m个单链表代表邻接矩阵的m行,即对图中的所有顶点都建立一个单链表,它把与顶点i邻接的顶点放在一个链表中。邻接表的每一个单链表的第一个节点存储有关顶点的信息,称它为表头节点,其余节点存放有关边的信息,称它为边表节点[3]。
共2页:
上一页
1
2
下一页
上一篇:
基于BootStrap框架的校园网站设计与实现
下一篇:
4G对移动电子商务的影响研究
基于Apriori算法的电影推荐
PHP+IOS的会议管理系统的设计+ER图
数据挖掘在电子商务中的应用
数据挖掘的主题标绘数据获取技术与实现
基于PageRank算法的网络数据分析
基于神经网络的验证码识别算法
基于网络的通用试题库系...
承德市事业单位档案管理...
神经外科重症监护病房患...
AT89C52单片机的超声波测距...
国内外图像分割技术研究现状
医院财务风险因素分析及管理措施【2367字】
志愿者活动的调查问卷表
中国学术生态细节考察《...
C#学校科研管理系统的设计
10万元能开儿童乐园吗,我...
公寓空调设计任务书