WarShall算法求传递闭包（可达矩阵） |
您所在的位置：网站首页 › 离散数学如何求传递闭包 › WarShall算法求传递闭包（可达矩阵） |
|
最近在复习离散数学，顺便记录记录自己对warshall算法的理解。
1、传递闭包（可达矩阵）
传递闭包是有向图的一个重要性质，它指的是在有向图中从任意一个节点出发，可以到达的所有节点的集合。在某些应用中，需要求解给定有向图的传递闭包，以便更好地分析和理解图的结构和性质。 2、WarShall算法步骤如下： （1）构造邻接矩阵根据有向图的边集构造一个邻接矩阵A，其中矩阵的每个元素表示一条边的权重或者是否存在边。 （2）初始化传递闭包矩阵构造一个大小和邻接矩阵相同的传递闭包矩阵A，初始化为邻接矩阵的值。 （3）迭代计算传递闭包矩阵对所有的j如果A[j,i]=1,则对k=1,2,3…,n都有A[j,k]=A[j,k] V A[i,k] （4）输出传递闭包矩阵最终的传递闭包矩阵即为求解结果，其中的每个元素表示两个节点之间是否存在路径。如果元素的值为1，则表示存在路径；否则表示不存在路径。 3、代码实现 #include using namespace std; int n; //n为矩阵的阶数 void warshall(int** matrix){ for(int i = 0;i if(matrix[j][i] == 1){ // 第j行与第i行进行或操作，并最终赋值到第j行 for(int k = 0;k cout cin >> matrix[i][j]; } } warshall(matrix); for(int i = 0;i cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |