首页 > 其他 > 详细

有向图的传递闭包

时间:2018-12-16 14:16:34      阅读:270      评论:0      收藏:0      [点我收藏+]

参考:https://wenku.baidu.com/view/0fdb85062af90242a995e504.html

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int v=4;
 4 const int N=10;
 5 bool g[N][N]={{0,1,0,0},{0,0,0,1},{0,0,0,0},{1,0,1,0}},temp[N][N];
 6 void floyd()//三重循环找闭包
 7 {
 8     for (int k=0;k<v;k++)//k为中间节点
 9     {
10         for (int i=0;i<v;i++)
11         {
12             for (int j=0;j<v;j++)
13             {
14                 temp[i][j]=g[i][j]||(g[i][k]&g[k][j]);
15             }
16         }
17         for (int i=0;i<v;i++)//把temp矩阵复制到g矩阵
18         {
19             for (int j=0;j<v;j++)
20             {
21                 g[i][j]=temp[i][j];
22             }
23         }
24     }
25     for (int i=0;i<v;i++)//输出
26     {
27         for (int j=0;j<v;j++)
28         {
29             printf("%2d ",temp[i][j]);
30         }
31         printf("\n");
32     }
33 }
34 int main()
35 {
36     cout<<"the number of vertex:\n"<<v<<endl;
37     cout<<"the original array:\n";
38     for (int i=0;i<v;i++)//输出原始矩阵
39     {
40         for (int j=0;j<v;j++)
41         {
42             printf("%2d ",g[i][j]);
43         }
44         printf("\n");
45     }
46     cout<<"the transitive closure:\n";
47     memset(temp,0,sizeof(temp));
48     floyd();
49 
50     return 0;
51 }

 

有向图的传递闭包

原文:https://www.cnblogs.com/hemeiwolong/p/10126310.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!