上一篇文章中我們簡(jiǎn)單介紹了什么是圖和圖分析,，圖分析的應(yīng)用場(chǎng)景和優(yōu)點(diǎn),，以及一些常用的圖工具，這篇文章里將介紹一下簡(jiǎn)單的圖遍歷算法,。

圖的遍歷

圖的遍歷是指,，從給定圖中任意指定的頂點(diǎn)（稱(chēng)為初始點(diǎn)）出發(fā)，按照某種搜索方法沿著圖的邊訪(fǎng)問(wèn)圖中的所有頂點(diǎn),，使每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次,，這個(gè)過(guò)程稱(chēng)為圖的遍歷。圖遍歷算法主要分為兩種：廣度優(yōu)先搜索和深度優(yōu)先搜索,。

廣度優(yōu)先搜索

廣度優(yōu)先搜索是從圖的一個(gè)頂點(diǎn)開(kāi)始,，向外一層一層地搜索，優(yōu)先訪(fǎng)問(wèn)所有相鄰頂點(diǎn),，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止的搜索方法,，如下圖所示：

             圖1                              圖2

             圖3                              圖4

圖1至4展示了在一張圖中依據(jù)廣度優(yōu)先算法得到的遍歷順序，可以很清楚地看見(jiàn)搜索順序是逐層往下,，將一個(gè)頂點(diǎn)的相鄰頂點(diǎn)全部遍歷完畢后再遍歷這些頂點(diǎn)的全部相鄰頂點(diǎn),，依次往下進(jìn)行。

深度優(yōu)先搜索

深度優(yōu)先搜索是深度優(yōu)先搜索的遍歷順序?yàn)樗阉饕粋€(gè)頂點(diǎn)的首個(gè)相鄰頂點(diǎn),，沿著一條路徑走到底然后回溯再走下一條路徑,，如下圖所示：

             圖5                              圖6

             圖7                              圖8

             圖9                    

從圖5至9可以明顯看到深度優(yōu)先遍歷與廣度優(yōu)先遍歷的區(qū)別，深度優(yōu)先遍歷每次只遍歷一個(gè)頂點(diǎn)的首個(gè)相鄰頂點(diǎn),，然后再遍歷該相鄰頂點(diǎn)的首個(gè)相鄰頂點(diǎn),，依次往下。

總結(jié)

以上就是對(duì)于基本的圖遍歷算法的介紹,，感興趣的朋友可以自己動(dòng)手嘗試,，在這里我推薦使用graphscope這個(gè)平臺(tái)。graphscope是阿里達(dá)摩院智能計(jì)算實(shí)驗(yàn)室研發(fā)并開(kāi)源的全球首個(gè)一站式超大規(guī)模分布式圖計(jì)算平臺(tái),，支持多種圖算法,，可以方便地進(jìn)行圖分析和圖計(jì)算，并且在性能上也達(dá)到極致,。在圖分析測(cè)試 LDBC GraphAnalytics Benchmark 上,，GraphScope 與PowerGraph 以及其他最新系統(tǒng)比較，幾乎在所有算法和數(shù)據(jù)集的組合中居于領(lǐng)先水平,。從下圖中我們可以看到,，在執(zhí)行廣度優(yōu)先遍歷算法（BFS）時(shí)，GraphScope用時(shí)0.23秒,，遠(yuǎn)小于PowerGraph的4.31秒,。

圖10

GraphScope 的白皮書(shū)、代碼已經(jīng)在github.com/alibaba/graphscope 開(kāi)源,，可以直接試用,。