圖的傳遞閉包模板

《圖的傳遞閉包模板》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、/*圖的傳遞閉包對(duì)于無(wú)向圖的傳遞閉包只需建邊是雙向建立傳遞閉包使用位運(yùn)算效率更高，使用bool型變量節(jié)省空間，該模板適用于G++編譯器算法基于Floyd算法思想,故實(shí)現(xiàn)傳遞閉包的函數(shù)命名為Floyd模板中點(diǎn)的編號(hào)為1~n而不是0~n-1模板的具體原理與證明請(qǐng)參考算法導(dǎo)論*/#includeconstintMAX=305;voidFloyd(bool(*mp)[MAX],intnum);intmain(void){inti;intj;intn;intm;intstart_node;intend_node;boolmap[MAX][MAX];//這些變量和數(shù)組可以在全局開(kāi)辟，

2、這樣Floyd函數(shù)中就不必傳遞參數(shù)了//實(shí)際題目中可能出現(xiàn)特殊的輸入結(jié)束條件，沒(méi)有限定都是按讀到EOF為止while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;++i){for(j=1;j<=n;++j){map[i][j]=false;}map[i][i]=true;}for(i=0;i

3、rue;無(wú)向圖需要建立另一條反向邊}Floyd(map,n);/*根據(jù)要求實(shí)現(xiàn)具體查詢*/}return0;}voidFloyd(bool(*mp)[MAX],intnum){inti;intj;intk;for(k=1;k<=num;++k){for(i=1;i<=num;++i){for(j=1;j<=num;++j){mp[i][j]=mp[i][j]

4、(mp[i][k]&mp[k][j]);}}}return;}