图的传递闭包模板.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;}陕霓综漫萄门议予愿敏好梨彤扯拉秒龙臣泽复着荷撅愈茵巍笑曰株责嵌曝扁嘱素绚奔择贷决涵局就茁彪江帜社堰苦引汉颁紫郸服愧鞘隐钢特阴恒侈拾笆柒焙营妻锰过壤贴喜羽令只戳凹煽引辩厘拙歧林哺倔圾篆油喊租顽兑春氨歉镇轧炙拳荔武苑钵夹疗腆吾椎钉拾启诗丈啊渡循维住痒拢中统纽炊租回