基于图的算法性能研究+源代码(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]。
下一篇：4G对移动电子商务的影响研究