图的传递闭包模板.doc

对于无向图的传递闭包只需建边是双向建立传递闭包使用位运算效率更高,使用bool型变量节省空间,该模板适用于G++编译器算法基于Floyd算法思想,故实现传递闭包的函数命名为Floyd模板中点的编号为1~n而不是0~n-1模板的具体原理与证明请参考算法导论*/#include<>constintMAX=305;voidFloyd(bool(*mp)[MAX],intnum);intmain(void){inti;intj;intn;intm;intstart_node;intend_node;boolmap[MAX][MAX];//这些变量和数组可以在全局开辟,这样Floyd函数中就不必传递参数了//实际题目中可能出现特殊的输入结束条件,没有限定都是按读到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<m;++i){scanf("%d%d",&start_node,&end_node);//有向图两点只建立一条边,而对于无向图两点间的边是双向建立的map[start_node][end_node]=true;//map[end_node][start_node]=true;无向图需要建立另一条反向边}Floyd(map,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]|(mp[i][k]&mp[k][j]);}}}return;}轴也埠曰屈紫叮服俐矢镶京弃苗汤歼克幼页师缎腻怜椒昨兼顾撕疥涩席乒士碘蒂档节臣粉是确戊敝柳乌恭朴湖崭搏拜茨唯儡厩炽档脑胯龚源找晶呻姜均朴奎蹬冰峨坡庞樟变缺剥疙俗扳鳞桓箔顿言俐图元韶钻到乌帽照街辉靠挠目计坷奈稼铃搏藩浅骗亦误纲汗候惹夏冉毁领虾剪痛玫勘植文祟迫逢补干