并行計算-實驗指導-實驗03圖論

1、實驗3圖論1傳遞閉包11.1傳遞閉包串行算法21.2傳遞閉包并行算法32連通分量52頂點倒塌法算法原理描述52.2連通分量并行算法53單源最短路徑73最短路徑串行算法73.2最短路徑并行算法84最小生成樹104最小生成樹串行算法114.2最小生成樹并行算法125小結(jié)14參考文獻15附錄 連通分量并行算法的mpi源程序15圖論在計算機科學、信息科學、人工智能、網(wǎng)絡理論、系統(tǒng)工程、控制論、運籌學和經(jīng)濟管理等領(lǐng)域 有著廣泛的應川。但很多圖論問題雖易表達，卻難以求解，其屮右相當多的圖論問題均屬np完全問題。 本章主要介紹工程實用簡單圖論問題的并行算法及其mpi編程實現(xiàn)，包括傳遞閉包、連通分量、最短路徑

2、 和最小生成樹等。1傳遞閉包設(shè)a是一個含n個頂點的有向圖g的布爾鄰接矩陣(boolean adjacent matrix),即元素aij=l當且僅當 從頂點i至u j有一條有向邊。所謂a的傳遞閉包(transitive closure),記為a+,是一個nxn的布爾矩陣, 其元素bij=l當且僅當：i=j；或從i出發(fā)存在有向路徑到j, 乂稱為頂點i到j可達。從g的布爾鄰接 矩陣a求出g的傳遞閉包，就稱為傳遞閉包問題。傳遞閉包問題有很強的應用背景，在科學計算中廣泛存在。傳遞閉包問題的經(jīng)典解法z就是利用布 爾矩陣的乘法來求解。本節(jié)將把這一算法分別在串行和并行機上實現(xiàn)。1.1傳遞閉包串行算法禾i川布

3、爾矩陣相乘求解傳遞閉包問題的原理為：對于布爾矩陣(a+護屮的任一元素by bi尸1表示從i 到j存在長度小于等于k的可達路徑，否則，切=0。顯然對于k=l, (a+i)'中切=1當且僅當從i到j路徑長 度為0 (冃)或為1 (從i到j存在有向邊)；(a+i)2中，bij=l當且僅當從i到j路徑長度小于等于2； (a+i)2) 2屮，bij=l當且僅當從i至1打路徑長度小于等于4,等等。因為任意兩點間如果存在可達路徑，長度最多為 n-1,所以kn-1時，(a+i)*就是所求的傳遞閉包a+。于是(a+i)矩陣的咤n次口乘z后所得的矩陣就是 所求的傳遞閉包。根據(jù)前面的敘述，很口然的有下面的傳

4、遞閉包串行算法15.1,其時間復雜度為0(n3log n)o算法151傳遞閉包串行算法輸入：圖g的布爾鄰接矩陣a輸出：a的傳遞閉包mprocedure closurebegin(1) 讀入矩陣a/*以下作a = a+i的運算*/(2) for i=0to n-l doa(i, i) = 1endfor/*以下是a矩陣的bgn次自乘，結(jié)果放入m矩陣；每次乘后，結(jié)果寫回a矩陣*/(3) for k=l to bg n do(3.1) for i=0 to n-l dofor j=0 to n-l dos=0while (s<n) and (a(i,s)=0 or a(s,j)=o) dos

5、= s+lendwhileif s<n then m(i,j)=l else m(i,j)=0endforendfor/*計算結(jié)果從m寫冋a*/(3.2)for i=0 to n-l dofor j=0 to n-l doa(i,j) = m(i,j)endforendforendforend(4.1) 2傳遞閉包并行算法本小節(jié)將把上一小節(jié)里的算法并行化。在圖論問題的并行化求解中，經(jīng)常使用將n個頂點(或連通分 fl)平均分配給p個處理器并行處理的皐木思想。其屮每個處理器分配到n個頂點，即n=n/po無法整除 時，一般的策略是在盡量均分的前提下，給最后一個處理器分配較少的頂點。為了使算法簡

6、明，在本章中， 僅在算法的mpi實現(xiàn)中才考慮不能整除的情況。在以后的幾節(jié)中，n、p、n都具有上面約定的意義，不再 多說。為了并行處理，這里將矩陣(a+i)進行劃分，分別交給p個處理粘。在每次矩陣乘法的計算中，將nx n的結(jié)果矩陣(a+i)2均勻劃分成pxp個子塊，每塊人小為nxn。處理器i負責計算位于第i子塊行上的p 個子塊。對整個子塊行的計算由p次循環(huán)完成，每次計算一個子塊。每個處理器為了計算一個nxn人小 的子塊，需要用到源矩陣(a+i)中對應的連續(xù)n行(局部數(shù)據(jù)a)和連續(xù)n列的數(shù)據(jù)(局部數(shù)據(jù)b)。計算完 成后，各處理器循環(huán)交換局部數(shù)據(jù)b,就可以進行下一個子塊的計算了。于是，總體算法由2層

7、循環(huán)構(gòu)成，外層是矩陣m=a+i的bgn次自乘，每次首先完成矩陣m的一次自 乘，然后將結(jié)果寫回m；內(nèi)層是p個子塊的計算，每次首先完成各口獨立的計算，然后處理器間循環(huán)交換 局部數(shù)據(jù)b°算法運行期間，矩陣m的數(shù)據(jù)作為全局數(shù)據(jù)由處理器()維護。根據(jù)以上思想，并行算法描述見下血的算法15.2,使用了 p個處理器，其時間復雜度為o(n3/p log n)o 其中myid是處理器編號，下同。算法152傳遞閉包并行算法輸入：圖g的布爾鄰接矩陣a輸出：a的傳遞閉包mprocedure closureparallelbegin/*由處理器0讀入矩陣a到m中，并進行“=1+1運算対應源程序中readmat

8、rix()函數(shù)*/(2) if myid=o then(2) 讀入矩陣a,放入m中(2) for i=0 to n-l dom(i,i)=lendforendif(3) 各處理器變量初始化/*以下是主循壞，矩陣m的bg n次自乘*/(4) for i=l to bg n par_do/*以下向各處理器發(fā)送對應子塊行和列數(shù)據(jù)對應源程序中scndmatrix()函數(shù)*/(4) for j=l to p-1 do(i )處理器0發(fā)送第j個子塊行的數(shù)據(jù)給處理器j,成為j的局部數(shù)據(jù)a(ii)處理器0發(fā)送第j個子塊列的數(shù)據(jù)給處理器j,成為j的局部數(shù)據(jù)bendfor/*以下是各處理器接收接收和初始化局部數(shù)據(jù)

9、a和b對應源程序屮getmatrix()i|數(shù)*/(4) 處理器0更新口己的局部數(shù)據(jù)a和b(4) 處理器1到p-1從處理器0接受數(shù)據(jù)，作為局部數(shù)據(jù)a和b/*以下是乘法運算過程，對應源稈序中paramul()函數(shù)*/(4) for j=0 to p-1 do(i )處理器k計算結(jié)果矩陣的子塊(k, (k+j) mod p)(ii) 各處理器將數(shù)據(jù)b發(fā)送給前一個處理器(iii) 各處理器從后一個處理器接收數(shù)據(jù)bendfor/*以下是各處理器將局部計算結(jié)果寫inlm數(shù)組對應源程序中writeback()j|數(shù)*/(4) if myid=0 then1 計算結(jié)果直接寫入矩陣m2 接受其它處理器發(fā)送來的

10、汁算結(jié)果并寫入melse發(fā)送計算結(jié)果的myid子塊行數(shù)據(jù)給處理器0endifendforendmpi源程序請參見所附光盤。2連通分量圖g的一個連通分量(connected component)是g的一個故大連通子圖，該子圖中每對頂點間均有一條 路徑。根據(jù)圖g,如何找出其所有連通分量的問題稱為連通分量問題。解決該問題常用的方法有3種： 使用某種形式的圖的搜索技術(shù)；通過圖的布爾鄰接矩陣計算傳遞閉包；頂點倒塌算法。本節(jié)將介紹如 何在并行環(huán)境下實現(xiàn)頂點倒塌算法。2. 1頂點倒塌法算法原理描述頂點倒塌(vertex collapse)算法中，一開始圖中的n個頂點看作n個孤立的超頂點(super vert

11、ex), 算法運行屮，有邊連通的超頂點相繼合并，直到形成最后的整個連通分量。每個頂點屬于旦僅屬于一個超 頂點，超頂點中標號最小者稱為該超頂點的根。該算法的流程由一系列循環(huán)組成。每次循環(huán)分為三步：發(fā)現(xiàn)每個頂點的最小標號鄰接超頂點；把 每個超頂點的根連到最小標號鄰接超頂點的根上；所有在第2步連接在一起的超頂點倒塌合并成為-個 較大的超頂點。圖g的頂點總數(shù)為n,因為超頂點的個數(shù)每次循環(huán)后至少減少一半，所以把每個連通分量倒塌成單個 超頂點至多咤n次循環(huán)即可。頂點i所屬的超頂點的根記為d(i),則一開始時有d(i)=i,算法結(jié)朿后， 所有處于同一連通分暈屮的頂點具有相同的d(i)o(4.2) 2連通分量

12、并行算法算法中為頂點設(shè)置數(shù)組變量d和c,其中d(i)為頂點i所在的超頂點號，c(i)為和頂點i或超頂點i相 連的最小超頂點號等，根據(jù)程序運行的階段不同，意義也佇變化。算法的主循環(huán)由5個步驟組成：各處 理器并行為每個頂點找出對應的c(i)；各處理器并行為每個超頂點找出最小鄰接超頂點，編號放入c(i) 中;修改所有d(i)二c;修改所有c(i)二c(c(i),運行bg n次；修改所有d(i)為c(i)和d(c(i)中較 小者。其中最后3步對應意義為超頂點的合并。頂點倒塌算法是專為并行程序設(shè)計的，多個頂點的處理具有很強的獨立性，很適合分配給多個處理器并行處理。這里讓p個處理器分管n個頂點。則頂點倒塌

13、算法的具體描述見算法15.3,使用了 p個處理器,其時間復雜度為o(n2/p log n),其中步驟(2)為主循環(huán)，內(nèi)含5個子步驟對應上面的描述。算法15.3頂點倒塌算法輸入：圖g的鄰接矩陣a輸出：向sd( 0 : n-1 )，其屮d(i)表示頂點i的標識procedure collapseerticesbegin/*初始化*/for 每個頂點 i par_dod(i) = iendforfor k=l to bg n do/*以下并行為每個頂點找鄰接超頂點屮最小的對應源程序中d_to_c()函數(shù)*/(2. 1) for 每個 i, j : 0 < i, j < n-1 par_d

14、oc(i) = min d(j) i a(i,j)=l and d(i)hd(j) if沒有滿足要求的d(j) thenc(i) = d(i)endifendfor/*以下并行求每個超頂點的故小鄰接超頂點対應源程序中c_to_c()函數(shù)*/(2. 2) for 每個 i, j: 0 < i, j < n-1 par_doc(i) = min c(j) i d(j)=i and c(j)hi if沒有滿足要求的c(j) thenc(i) = d(i)endifendfor(2. 3) for 每個 i: 0 < i < n-1 par_dod(d = c(i)endfor

15、(2. 4) for i=l to log n do/*以下対應源程序中cc_to_c()函數(shù)*/for 每個 j: 0 < j < n-l par_doc(j) = c(c(j)endforendfor/*以下對應源程序中cd_to_d()函數(shù)*/(2. 5) for 每個 i: 0<i <n-l par_dod(i) = min c(i), d(c(i) endforendforendmpi源程序請參見章末附錄。3單源最短路徑單源最短路徑(single source shortest pa(h)問題是指求從一個指定頂點s到其它所有頂點i之間的距離, 因為是單一頂點到

16、其它頂點的距離，所以稱為單源。設(shè)圖g(v,e)是一個有向加權(quán)網(wǎng)絡，其中v和e分別 為頂點集合和邊集合,其邊權(quán)鄰接矩陣為w,邊上權(quán)值w(i,j)>0, ijev, v=o,1,n1。設(shè)dist( i)為最短的路徑長度,即距離，其中swv且ihs。這里采用著名的dijkstra算法,并將其并行 化。(4.3) 1最短路徑串行算法dijkstra算法(dijkstra algorithm)是單源最短路徑問題的經(jīng)典解法之一，基本思想如下。假定有一個待搜索的頂點表vl,初始化時做：dist(s)-o, dist(i)=oo(is), vl=v0每次從vl (非空集)中選取這樣的一個頂點u,它的di

17、sl(u)最小。將選出的u點作為搜索頂點，對于其它還在vl 內(nèi)的頂點 v,若<u,v>e e,而且 dist(u)+w(u,v)<dist(v),則更新 dist(v)為 dist(u)+w(u,v),同時從 vl 中將 u 刪 除，立到vl成為空集時算法終止。算法15.4中給出了最短路徑問題的dijkstra串行算法，其時間復雜度為0(川)。算法154dijkstra串行算法輸入：邊權(quán)鄰接矩陣w (約定頂點i, j之間無邊連接時w(i,j)=°°, jlw(i,i) = o)、 待計算頂點的標號s輸出：dist(o:n-l),其中disl(i)表示頂點s

18、到頂點i的最短路徑(lwiwn)procedure dijkstrabegindist(s) = 0for i=0 to n-l doif is then dist(i) = 00endforvl = v for i=0 to n-l do從vl中找一個頂點u,使得dist(u)最小for (每個頂點 vg vl) and (<u,v>e) doif dist(u)+w(u,v)<dist(v) then dist(v) = dist(u)+w(u,v)endifendfor(5) vl = vl-uendforend3. 2最短路徑并行算法在上一小節(jié)串行算法的基礎(chǔ)上，這里將

19、其并行化。思路如下：上述算法的(1) (2)兩步中，每個處理器分派n=n/p個節(jié)點進行初始化。第(4.1)步可以并行化為：首先每個處理器分派n個節(jié)點分別求局部最小值，然后再p個處理器合 作求全局最小值，最后再將這一最小值廣播出去。p個處理器合作方法如下：當p為偶數(shù)時，后p/2個處 理器將自己的局部最小值分別發(fā)送到對應的前p/2個處理器中，山前p/2個處理器比較出2個局部最小值 中相對較小者并保留。當p為奇數(shù)時，設(shè)p二2h+l,則后h個處理器的值分別發(fā)送到前h個處理器中，比較 并保留小值。一次這樣的循環(huán)過后，p個最小值減少了一半，兩次后，變?yōu)?/4,如此一層一層的比較， bgp次循環(huán)后，就可以得

20、出唯一的全局最小值。第(4.2)步可以每個處理器分配n個頂點，然后獨立進行更新dist的操作。根據(jù)以上思路，最短路徑的并行算法見算法15.5,使用了 p個處理器，其時間復雜度為0(n2/p+n bg p)o這里的實現(xiàn)算法和對應的源程序中，處理器0只進行輸入輸出工作，不參與任何其它計算；因此實際 參加運算的處理器為p-l個，所以有n=n/(p-l)；另外，布爾數(shù)組bdist用來標記各頂點是否已從vl中取 出。算法15.5 dijkstra并行算法輸入：邊權(quán)鄰接矩陣w (約定頂點i, jz間無邊連接時w(i,j)=oo,且w(i,i) = 0)、待計算頂點的標號s輸出：dist(o : n-1),

21、其中dist(i)表示頂點s到頂點i的最短路徑(i wiwn)procedure dijkstra-parallelbegin/*以卜對應源程序中readmatrix()l|數(shù)*/處理器0讀入邊權(quán)鄰接矩陣w/*以下初始化dist和bdist數(shù)組,對應源程序中init()函數(shù)*/for 每個頂點 i par_doif i=s thendist(i) = 0bdist(i) = trueelsedist(i) = w(i,s)bdisl(i) = falseendifendfor/*以下是算法主循壞，對應源程序中findminwayo函數(shù)*/for i=l to n-l do/*各處理器找出口己負

22、責范圍內(nèi)未搜索節(jié)點中授小的dist */(3.1) for 每個頂點 j par_doindex = min j i bdist(j)=false num = dist(index)/*以下各處理器協(xié)作對p-l個index求最小*/cal num = p-1for j=l to log(p-l) par_doif cal num mod 2=0 then 本次循環(huán)參加比較的數(shù)據(jù)個數(shù)為偶數(shù)(i ) calnum = calnum/2序號大丁 calnum的處理器將index和num發(fā)送給序號比口己小 calnum的處理器序號小于calnum的處理器(不包含0號)在自己原有的和收到 的兩個num之

23、間，比較并保留較小者，同時記錄對應的indexelse本次循壞參加比較的數(shù)據(jù)個數(shù)為奇數(shù)(i ) calnum = (calnum+l)/2序號大于calnum的處理器將index和num發(fā)送給序號比口己小 calnum的處理器序號小于calnum的處理器(不包含0號)在自己原有的和收到 的兩個num z間，比較并保留較小者，同時記錄對應的indexendifendfor處理器1廣播通知其它處理器自己的num和index/*以下并行更新*/for 每個頂點 j par_doif bdist(j)=false then dist(j) = niin dist(j), num+w(j,index)

24、endifendfor頂點index對應處理器將對應的bdist(index)更改為trueendforendmpi源程序請參見所附光盤。4最小生成樹一個無向連通圖g的牛成樹是指滿足如下條件的g的子圖t：t和g頂點數(shù)相同；t有足夠的邊使得所有頂點連通，同時不出現(xiàn)回路。如果對g的每條邊指定一個權(quán)值，那么，邊權(quán)總和最小的生成樹稱 為最小代價生成樹，記為mcst (minimum cost spanning tree),常簡稱為最小生成樹(記為mst)。最 小生成樹問題就是給定g,找出g的一個最小生成樹t的問題。木節(jié)將介紹川于求解mst問題的sollin算法，并將其實現(xiàn)。4.1最小生成樹串行算法so

25、llin算法(sollin algorithm)是眾多川于求解mst問題的算法之一，其原理為：算法開始時，圖屮的 n個頂點視為一片森林，每個頂點視為一棵樹；算法主循環(huán)的流程中，森林里每棵樹同時決定其連向其它 樹的最小鄰邊，并將這些邊加入森林中，實現(xiàn)樹的合并；循環(huán)到森林中只剩一棵樹時終止。由于森林中樹 的數(shù)日每次至少減少一半，所以只要bgn次循壞就可以找出msto算法中以d(i)為頂點i所在的樹的編號，cdgc(i)和closct(i)為樹i連向其它樹的最小鄰邊和其t度， 則sollin算法的形式描述見算法15.6,其時間復雜度為0(n2 log n)。算法 15.6 sollin mst 算法

26、輸入：無向圖g的邊權(quán)矩陣w輸出：g的最小生成樹的邊集合tprocedure sollin-mstbegin/*以下所有頂點初始化為一棵孤立的樹*/for i=0 to n-1 dod(i) = iendfort初始化為空集while iti < n-l do/*以下為各樹尋找連向其它樹的最小邊權(quán)*/for 每棵樹 i docloset(i) = 00endforfor 圖 g 中每條邊(v,u) doif d(v)hd(u) and w(v,u)<closet(d(v) then(i ) closet(d(v) = w(v,u)(ii) edge(d(v) = (v,u)/*以下是

27、樹的合并*/(3.3) for 每棵樹 i do(i ) (v,u) edge(i)(ii) if d(v)hd(u) thent = t+(v,u)樹d(v)和d(u)合并endifendforendwhileend(4.4) 2最小生成樹并行算法在上一小節(jié)sollin算法的基礎(chǔ)上，本節(jié)將其并行化?；舅悸肥鞘卸鄠€處理器同時負責為多個樹查找 最短邊。為了方便并行處理，各樹尋找外連最短邊的的任務分兩步進行：所有處理器獨立并行為每個頂 點找連向其它樹的最短邊，并將這些數(shù)據(jù)保存；各處理器獨立并行檢索每棵樹的各頂點，為整棵樹找出 外連最短邊。注意在以上兩步中，處理器間分別按照頂點和樹進行分配，對象有

28、了變化。為了配合算法運行，設(shè)置了 4個一維數(shù)組d、c、j、w：d(i)為頂點i所在的樹的編號，也就是該 樹中最初的頂點號，初始化為i;c(i)為離頂點i最近的其它樹的編號；j(i)為對應的頂點號；w(i) 為對應的邊權(quán)，即距離。以上變暈約定對mst并行算法的源程序同樣適用。運行期間每個處理辭處理n=n/p 個頂點或n個連通分量。各樹找出外連最短邊后，接下來分3步進行樹的合并：讓所有的d(i)=c(i)；對所有i,進行 c(i)=c(c(i)運算，并循環(huán)bg n次；對所有i,更新d(i)為c(i)和d(c(i)中較小者。以上合并過程類似頂 點倒塌算法中超頂點的合并。設(shè)mst為輸出的最小生成樹的鄰

29、接矩陣，運行期間由0號處理器維護，則并行算法的描述見算法15.7, 使用了 p個處理器，其時間復雜度為o(n?/p log n)o算法15.7并行sollin mst算法輸入：原始圖g的鄰接矩陣a輸出：所求最小牛成樹的鄰接矩陣mstprocedure sollin-mst-parallelbegin/*以下初始化將圖初始化為n棵樹*/for每個頂點i par_dod(i) = iendfor(2) while圖g未連通do/*以下各處理器為所負責的頂點找出距離最近的樹 對應源程序中d_to_c()函數(shù)*/for 每個頂點 i par_do(i ) w(i) = maxfor每個頂點j doif

30、 a(i, j)>0 and d(j)hd(i) and a(i, j)<w(i) then c(i) = d(j)w(i) = a(i,j)endifendforifw(i)=maxthenc(i) = d(i)endifendfor/*以下各處理器為所負責的樹找出外連的最短邊 對應源程序中c_to_c()函數(shù)*/for 每棵樹 i par_do(i ) tempj = n+ltempw = maxfor每個頂點j doif d(j)=i and c(j)hi and w(j)<tempw thenc(i) = c(j)tempw = w(j)tempj = j(iv) i

31、f tempj<n and j(tempj)<n then通知處理器0將邊(tempj, j(tempj)加入mst數(shù)組endifendforfor i=0 to n-l par_dod(i) = c(i)endforfor i= 1 to bg n do/*以下對應源程序中cc_to_c()函數(shù)*/for j=0 to n-l par_doc(j) = c(c(j)endforendfor/*以下對應源程序中cd_to_d()函數(shù)*/for i=0 to n-l par_dod= min c(i), d(c(i) endforendwhileendmpi源程序請參見所附光盤。5小

32、結(jié)本章針對傳遞閉包、連通分量、單源最短路徑、最小牛成樹等4個經(jīng)典圖論問題，分別介紹了它們的 -種典型算法，以及在mpi并行環(huán)境下的算法實現(xiàn)。其屮除連通分量外，其它3個問題的并行算法實現(xiàn)均 由串行算法并行化而得到；通過這3個問題，較為詳細的介紹了圖論問題串行解法并行化的一般思路：均 勻數(shù)據(jù)劃分，獨立計算。如何劃分才能盡量做到計算的獨立，是劃分的關(guān)鍵。在最小生成樹sollin算法的 并行化中，其至在程序運行中按照不同的對彖對數(shù)據(jù)進行了劃分。除了常見的串行算法并行化z外，本章還通過連通分量問題的解法，接觸了根據(jù)并行機特點，直接為并行環(huán)境設(shè)計的圖論問題解法。這種情況在非數(shù)值算法問題中并菲特例。int

33、p;int *d,*c;int *a;int temp;int myid;mpi_status status;/*輸出必要信息*/void print(int *p)int i;if(myid=0)for(i=0;i<n;i+)printf(h%d “,pi);printf(mnh);本章的編寫主要參考了文獻。其中，并行傳遞閉包和連通分量算法也可以參見文獻，單源最短路 徑dijkstra算法也町以參見文獻，而最小生成樹sollin算法也對以參見文獻叫參考文獻.陳國良編著.并行算法的設(shè)計與分析(修訂版)高等教育出版社,2002.11. hirschberg d s. parallel al

34、gorithms for transitive closure and the connected component problem. proc. 8thannu. acm stoc, new york, 1976,55-57. dijkstra e. a note on two problems in connetion with graphs. numerische mathematic, 1959,1:269-271. goodman s e and hedetnimi s t ed. introduction to the design and analysis of algorit

35、hms(in an algorithmattributed to sollin). mcgraw-hill, new york, 1977附錄連通分量并行算法的mpi源程序1.源程序 connect.c/*本算法中處理器數(shù)忖須小于圖的頂點數(shù)*/#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <math.h>#includc <mpi.h>/*使用動態(tài)分配的內(nèi)存存儲鄰接矩陣，以下為宏定義*/#define a(i,j) ai*n+j嚴以下為n:頂點數(shù)n:各

36、處理器分配的頂點數(shù)p:處理器數(shù)*/intn;int n;/*讀入鄰接矩陣*/void reada()char * filename;int ij;printf("n");printf("input the vertex num:n");scanf(”d”,&n);n=n/p;if(n%p!=0) n+;a=(int*)malloc(sizeof(int)*(n*p)*n);if(a=null)printf(uerror when allocating memory'n");cxit(o);printf("input t

37、he adjacent matrix:nh);for(i=0;i<n;i+)for(j=0;j<n;j+)scanf("%d'&a(i,j);for(i=n;i<n*p;i+)for(j=0;jvn;j+)a(i,j)=o;/*處理器0廣播特定數(shù)據(jù)*/void bcast(int *p)mpi_bcast(p,n ,mpint,0,mpi_comm_world);/*兩者中取最小的數(shù)沖函數(shù)*/int min(int a,int b)return(a<b?a:b);)/*為各頂點找最小的鄰接超頂點，對應算法步驟(2.1)*/void d_to_c

38、()int i,j；for(i=0;i<n;i+)cn*myid+i=n+l;for(j=0;j<n;j+)if(a(i,j)=l)&&(dj!=dn*myid+i)&&(d|j<cn*myid4-ij)cn*myid+i=dj;if(cn*myid+i=n+l)cn*myid+i=dn*myid+i;/*為各超頂點找故小鄰接超頂點，對應算法步驟(2.2)*/void c_to_c()int i,j；for(i=0;i<n;i+) temp=n+1;for(j=0;j<n;j+) if(dj=n*myid+i)&&(

39、cj!=n*myid+i)&&(c|jl<temp)temp=c|j;if(temp=n+l) temp=dn*myid+i ;cmyid*n+i=temp;)嚴調(diào)整超頂點標識*/void cc_to_c()int i;for(i=0;i<n;i+)cfmyid*n+i=ccmyid*n+i;/*產(chǎn)生新的超頂點，對應算法步驟(2.5)*/void cd_to_d()int i;for(i=0;i<n;i+)dmyid*n+ij=min(cniyid*n+i,dcmyid*n+i)；/*釋放動態(tài)內(nèi)存*/void freeall()free(a);free(d);

40、free(c);/*主函數(shù)*/void main(int argc,char *argv)int i,j,k;double 1;int group_size;嚴以下變量用來記錄運行時間*/double starttime,endtime;mpi_i nit(&argc,&argv);mpi comm size(mpi comm world,& group_size);mpi comm rank(mpi comm world,& myid);p=group_sizc;mpi_barrier(mpi_comm_world);if(myid=0)starttime=m

41、pi_wtime();/*處理器0讀鄰接矩陣*/if(myid=0) reada();mpi_barrier(mpi_comm_world);mpi_bcast(&n, 1,mpi_int,o,mpi_comm_world);if(myid!=0)(n=n/p;if(n%p!二0) n+;)d=(int*)malloc(sizeof(int)*(n*p);c=(int*)malloc(sizeof(int)*(n*p);if(myid!=0)a=(int*)malloc(sizeof(int)*n*n);/*初始化數(shù)組d,步驟*/for(i=0;i<n;i+) dmyid*n+i=myid*n+i;mpi_baitier(mpi_comm_world);mpi_gather( &dmyid*n,n,mpint,d,mpint,0,mpi_comm_world)；bcast(d);mpi_barrier(mpi