基于图论的Randic指标极图的算法研究

彭卓宇

摘要：本文通过分析图的结构，用邻接链表的方法使用C++语言对Randic指标极大值以及连通的路径进行了搜索，从而找出相应的路径。

Abstract： This paper analyzes the structure of the graph and uses the adjacency linked list method to search the maximum value of Randic index and connected paths using C ++ language to find the corresponding paths.

关键词：Randic指标;极图;算法研究

1  图的简介

图由一系列的点和描述点之间的关系边（弧）组成，这些数据元素被相互连接以形成网络。其形式化定义为：G=（V，E），V={Vi|Vi∈ 某个数据元素集合}，其中，G表示图，V是顶点的集合，E是边或者弧的集合。在集合E中，P（Vi，Vj）表示顶点Vi和顶点Vj之间有边或弧相连。而在计算机中，通常将连通图和邻接矩阵或者邻接链表等联系在一起用于解决问题，从而寻找其连通路径。

2  极大值点的选择

若一无向连通图G，通过邻接链表寻找其Randic指标的极大值和连通路径，需找出连通图G=（V，E）中最大度的点，并以此作为起点start，且如果度最大的点有多个，需要人为指定其中两个并保证二者相连;如果最大度的点只有一个，而度排序第二的点有多个的，也需要人为指定，故文档中的源程序不计算度大的点，其值由人为指定。由无向连通图G的相关定义可知：如果G=（V，E）连通，则本文提到的图都是满足于此条件的图。

3  数学建模

①用数学知识来建模：分子的Randic指标是从化学图集合到实数集合的一个映射，我们结合离散数学中的图论知识，用连通图来表示Randic指标。在计算机中，可以用邻接链表来将连通图存储下来。

②借助C++语言编程实现寻找连通路径：设所给图G初始的所有点均未被访问过，在G中选一最大度点S为出发点，首先访问出发点S，且将其标记为已访问状态;然后依次从S出发访问S的每个邻接点。如果邻接点未曾访问过，则以邻接点为新的出发点，继续访问其邻接点，直至图中所有和点S有路径相通的点均已被访问为止。

4  算法编程实现

根据图1中的无向连通图，0为度最大的点，而4或5为度第二大的点，则可以设点0为初始点，点5位终点，则有如图2结果。

程序源代码部分：

参考文献：

[1]李春葆.数据结构教程[M].清华大学出版社，2017.

[2]王晓东.算法设计与分析[M].电子工业出版社，2017.

[3]梁磊.两点间所有路徑的遍历算法[J]. 科技信息，2010/11/25.