基于圖論的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.