图的传递闭包模板

《图的传递闭包模板》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*图的传递闭包对于无向图的传递闭包只需建边是双向建立传递闭包使用位运算效率更高，使用bool型变量节省空间，该模板适用于G++编译器算法基于Floyd算法思想,故实现传递闭包的函数命名为Floyd模板中点的编号为1~n而不是0~n-1模板的具体原理与证明请参考算法导论*/#includeconstintMAX=305;voidFloyd(bool(*mp)[MAX],intnum);intmain(void){inti;intj;intn;intm;intstart_node;intend_node;boolmap[MAX][MAX];//这些变量和数组可以在全局开辟，

2、这样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

3、rue;无向图需要建立另一条反向边}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]

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