基于圖論的Randic指標(biāo)極圖的算法研究

彭卓宇

摘要：本文通過分析圖的結(jié)構(gòu)，用鄰接鏈表的方法使用C++語言對Randic指標(biāo)極大值以及連通的路徑進(jìn)行了搜索，從而找出相應(yīng)的路徑。

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.

關(guān)鍵詞：Randic指標(biāo);極圖;算法研究

1? 圖的簡介

圖由一系列的點(diǎn)和描述點(diǎn)之間的關(guān)系邊（?。┙M成，這些數(shù)據(jù)元素被相互連接以形成網(wǎng)絡(luò)。其形式化定義為：G=（V，E），V={Vi|Vi∈ 某個(gè)數(shù)據(jù)元素集合}，其中，G表示圖，V是頂點(diǎn)的集合，E是邊或者弧的集合。在集合E中，P（Vi，Vj）表示頂點(diǎn)Vi和頂點(diǎn)Vj之間有邊或弧相連。而在計(jì)算機(jī)中，通常將連通圖和鄰接矩陣或者鄰接鏈表等聯(lián)系在一起用于解決問題，從而尋找其連通路徑。

2? 極大值點(diǎn)的選擇

若一無向連通圖G，通過鄰接鏈表尋找其Randic指標(biāo)的極大值和連通路徑，需找出連通圖G=（V，E）中最大度的點(diǎn)，并以此作為起點(diǎn)start，且如果度最大的點(diǎn)有多個(gè)，需要人為指定其中兩個(gè)并保證二者相連;如果最大度的點(diǎn)只有一個(gè)，而度排序第二的點(diǎn)有多個(gè)的，也需要人為指定，故文檔中的源程序不計(jì)算度大的點(diǎn)，其值由人為指定。由無向連通圖G的相關(guān)定義可知：如果G=（V，E）連通，則本文提到的圖都是滿足于此條件的圖。

3? 數(shù)學(xué)建模

①用數(shù)學(xué)知識來建模：分子的Randic指標(biāo)是從化學(xué)圖集合到實(shí)數(shù)集合的一個(gè)映射，我們結(jié)合離散數(shù)學(xué)中的圖論知識，用連通圖來表示Randic指標(biāo)。在計(jì)算機(jī)中，可以用鄰接鏈表來將連通圖存儲下來。

②借助C++語言編程實(shí)現(xiàn)尋找連通路徑：設(shè)所給圖G初始的所有點(diǎn)均未被訪問過，在G中選一最大度點(diǎn)S為出發(fā)點(diǎn)，首先訪問出發(fā)點(diǎn)S，且將其標(biāo)記為已訪問狀態(tài);然后依次從S出發(fā)訪問S的每個(gè)鄰接點(diǎn)。如果鄰接點(diǎn)未曾訪問過，則以鄰接點(diǎn)為新的出發(fā)點(diǎn)，繼續(xù)訪問其鄰接點(diǎn)，直至圖中所有和點(diǎn)S有路徑相通的點(diǎn)均已被訪問為止。

4? 算法編程實(shí)現(xiàn)

根據(jù)圖1中的無向連通圖，0為度最大的點(diǎn)，而4或5為度第二大的點(diǎn)，則可以設(shè)點(diǎn)0為初始點(diǎn)，點(diǎn)5位終點(diǎn)，則有如圖2結(jié)果。

程序源代碼部分：

參考文獻(xiàn)：

[1]李春葆.數(shù)據(jù)結(jié)構(gòu)教程[M].清華大學(xué)出版社，2017.

[2]王曉東.算法設(shè)計(jì)與分析[M].電子工業(yè)出版社，2017.

[3]梁磊.兩點(diǎn)間所有路徑的遍歷算法[J]. 科技信息，2010/11/25.