1、隨著計(jì)算機(jī)科學(xué)的不斷發(fā)展，圖的搜索技術(shù)已經(jīng)滲透到語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電子、通信、數(shù)學(xué)等諸多學(xué)科領(lǐng)域，特別是網(wǎng)絡(luò)技術(shù)的快速發(fā)展和并行計(jì)算機(jī)的出現(xiàn)，并行處理進(jìn)入了前所未有的繁榮期，圖的遍歷也顯得越來(lái)越重要。廣度優(yōu)先搜索算法是圖論的一個(gè)基本問(wèn)題，也是一個(gè)熱點(diǎn)問(wèn)題。廣度優(yōu)先搜索算法的并行化已經(jīng)成為目前亟待解決的問(wèn)題。
　　本文首先介紹了廣度優(yōu)先搜索并行算法的研究現(xiàn)狀。然后，在Cilk++運(yùn)行時(shí)系統(tǒng)上，實(shí)現(xiàn)了用“bag”的數(shù)據(jù)結(jié)構(gòu)代

2、替共享隊(duì)列的一種優(yōu)化方法，該算法是基于層同步思想的一個(gè)細(xì)粒度并行算法，能夠更容易的并行代碼。其次，在分布式系統(tǒng)上，實(shí)現(xiàn)了基于鄰接矩陣一維劃分的并行廣度優(yōu)先搜索算法。最后，在分析和研究現(xiàn)有的廣度優(yōu)先搜索并行算法的基礎(chǔ)上，結(jié)合現(xiàn)有的并行計(jì)算環(huán)境，提出了一種新的廣度優(yōu)先搜索并行算法。該算法是在分布式系統(tǒng)上提出來(lái)的，結(jié)合了層同步的思想和鄰接矩陣二維劃分的思想。通過(guò)大量實(shí)驗(yàn)證明，我們提出的新算法在時(shí)間復(fù)雜度上達(dá)到了更好的性能，在分布式系統(tǒng)上具有更