精华内容
下载资源
问答
  • Warshall算法求传递闭包

    万次阅读 多人点赞 2017-03-30 07:05:38
    传递闭包的一种有效算法—Warshall算法,这种算法也便于计算机实现。 (1)置新矩阵A=M; (2)i=1; (3)对所有j如果A[j,i]=1,则对k=1,2,…,n,A[j,k]=A[j,k]∨A[i,k]; (4)i加1;(i是行,j是列) (5...

    算法描述:
    传递闭包的一种有效算法—Warshall算法,这种算法也便于计算机实现。
    (1)置新矩阵A=M;
    (2)i=1;
    (3)对所有j如果A[j,i]=1,则对k=1,2,…,n,A[j,k]=A[j,k]∨A[i,k];
    (4)i加1;(i是行,j是列)
    (5)如果i≤n,则转到步骤3),否则停止。
    例如:
    这里写图片描述
    这里写图片描述
    这里写图片描述
    代码:

    #include <stdio.h>
    #define N 4    //宏定义 
    int get_matrix(int a[N][N])
    {
        int i = 0,j = 0;
        for (i = 0;i < N;i++) 
        {
            for (j = 0;j < N;j++)
             {
                scanf("%d",&a[i][j]);
                if (a[i][j] != 0 && a[i][j] != 1)
                    return 1;            
             }
        }
        return 0;
    }
    int output_matrix(int a[N][N])
    {
        int i = 0,j = 0;
        for (i = 0;i < N;i++) {
            for (j = 0;j < N;j++) {
                printf("%d  ",a[i][j]);
            }
            putchar('\n');
        }
    }
    int warshall(int a[][N])
    {    
        //(1)i=1;
        //(2)对所有j如果a[j,i]=1,则对k=0,1,…,n-1,a[j,k]=a[j,k]∨a[i,k];
        //(3)i加1;
        //(4)如果i<n,则转到步骤2,否则停止
        int i = 0;
        int j = 0;
        int k = 0;
        for (i = 0;i < N;i++) 
        {                  
            for (j = 0;j < N;j++) 
            {
                if (a[j][i]) 
                {
                    for (k = 0;k < N;k++) 
                    {
                        a[j][k] = a[j][k] | a[i][k];//逻辑加 
                    }
                } 
            }
        }
    }
    int main()
    {
        int a[N][N] = {0};
        printf("please input a matrix with %d * %d:\n",N,N);
        if (get_matrix(a))
         {  printf("Get matrix error!Only 0 or 1 in matrix!\n");
            return 1; //错误返回主函数,返回值为1; 
         }
        warshall(a);
        output_matrix(a);
    
        return 0;//正常返回主函数,返回值为0; 
    }
    
    
    展开全文
  • Warshall算法求传递闭包python实现 算法描述: Warshall在1962年提出了一个关系的传递闭包的有效算法。其具体过程如下,设在n个元素的有限集上关系R的关系矩阵为M: (1)置新矩阵A=M; (2)i=1; (3)对所有j如果A...
  • Warshall 算法 Wk−1W_{k-1}Wk−1​第k列元素遍乘第k行元素加到矩阵Wk−1W_{k-1}Wk−1​ 初始矩阵 [0100101000010000] \left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 &...

    原理

    W k − 1 W_{k-1} Wk1第k列元素遍乘第k行元素加到矩阵 W k − 1 W_{k-1} Wk1
    在这里插入图片描述

    举例

    初始矩阵
    [ 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 ] \left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{matrix} \right] 0100100001000010
    W1:第一列(2,1),第一行(1,2) →(2,2)
    [ 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 ] \left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{matrix} \right] 0100110001000010
    W2:第二列(1,2)、(2,2),第二行(2,1)、(2,2)、(2,3)
    →(1,1)、(1,2)、(1,3)、(2,1)、(2,2)、(2,3)
    [ 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 ] \left[ \begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{matrix} \right] 1100110011000010
    W3:第三列(1,3)、(2,3),第三行(3,4)→(1,4)、2,4)
    [ 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 ] \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{matrix} \right] 1100110011001110
    W4:第四列没有1,矩阵不能继续更新,所以传递闭包即为W3.

    展开全文
  • Warshall算法求传递闭包1、算法描述:2、例题:3、Python代码实现4、参考文章: 1、算法描述: 传递闭包的一种有效算法—Warshall算法,这种算法也便于计算机实现。 (1)、置新矩阵A=M; (2) 、i=1; (3)、对所有...

    1、算法描述:

    传递闭包的一种有效算法—Warshall算法,这种算法也便于计算机实现。

    • (1)、置新矩阵A=M;
    • (2) 、i=1;
    • (3)、对所有j如果A[j,i]=1,则对k=1,2,…,n,A[j,k]=A[j,k]∨A[i,k];
    • (4)、i加1;(i是行,j是列)
    • (5)、如果i≤n,则转到步骤3),否则停止。

    2、例题:

    在这里插入图片描述

    3、Python代码实现

    Matrix = []  # 声明空矩阵
    n = int(input('请输入矩阵阶数: \n'))  # 将输入的数字整型化赋给n
    
    # 获取矩阵关系
    for i in range(n):  # 从0到n-1依次取值
        Matrix.append(input('第{}行 :'.format(i + 1)).split())
    
    
    # 逻辑加(或运算)
    def logicAdd(a, b):
        if a == 0 and b == 0:
            return 0
        else:
            return 1
    
    
    # Walshall算法求传递闭包
    for column in range(n):  # 从第一列到第n列[range()函数从0到n-1但是不影响算法]
        for row in range(n):  # 从第一行到第n行[range()函数从0到n-1但是不影响算法]
            # row的for循环在column的for循环的下面,在行数确定时,对相应列的所有元素进行遍历,变化的是row行数
            if int(Matrix[row][column]) == 1:  # 判断第row行第column行的元素是否为1
                for i in range(n):  # 计算n次
                    Matrix[row][i] = logicAdd(int(Matrix[row][i]), int(Matrix[column][i]))
    # 将该行的所有元素与对应行的元素进行逻辑加运算,此处,因为行数与列数是相同的,所以用column固定值表示
    
    print("根据Warshall算法求得的传递闭包如下 :↓↓↓")
    # 打印结果
    for row in range(n):
        for column in range(n):
            print(Matrix[row][column], end='  ')
        print()
    # 该算法的核心是:从矩阵的第一行开始,查看第一列的元素,如果有值为1,则将该1值所处的行数的所有元素与第一行的对应元素进行逻辑加运算;依次计算......
    
    

    运行截图:
    在这里插入图片描述

    4、参考文章:

    • https://blog.csdn.net/foreverzili/article/details/68481930
    • https://www.cnblogs.com/wwbsun/p/12801456.html
    展开全文
  • warshall算法求传递闭包transitive closurewarshall算法传递闭包完整源码 warshall算法求传递闭包完整源码 #include <stdbool.h> #include <stdio.h> #define NODES 4 int digraph[NODES][NODES] ...

    用warshall算法求传递闭包transitive closure

    warshall算法求传递闭包完整源码

    #include <stdbool.h>
    #include <stdio.h>
    
    #define NODES 4
    
    int digraph[NODES][NODES] = {
       
        {
       
    展开全文
  • Warshall算法求传递闭包(python) 算法描述: Warshall在1962年提出了一个关系的传递闭包的有效算法。其具体过程如下,设在n个元素的有限集上关系R的关系矩阵为M: (1)置新矩阵A=M; (2)i=1; (3)对所有j如果A...
  • 传递闭包有一种有效算法—Warshall算法,这种算法也便于计算机实现。  (1)置新矩阵A=M;  (2)i=1;  (3)对所有j如果A[j,i]=1,则对k=1,2,…,n,A[j,k]=A[j,k]∨A[i,k](这里的加是布尔加);  (4)i...
  • Floyd-Warshall算法是求解任意两点最短路的有力武器。其也适用于存在负边的情况。DP思路,假设只使用前K个点时i到j的最短距离为d[k][i][j] 那么,使用前K+1个点就可以分成两种情况 ①i到j的最短路用到了第K+1个点...
  • 传递闭包 在数学中,在集合 X 上的二元关系 R 的传递闭包是包含 R 的 X 上的最小的传递关系。 例如,如果 X 是(生或死)人的集合而 R 是关系“为父子”,则 R 的传递闭包是关系“x 是 y 的祖先”。...Warshall...
  • 利用WarShall算法求解过程如下: 从第一列元素,开始看,哪个为1,可以看出,<1,1>,<2,1>,<4,1>为1,则分别将第1、2、4行元素与第1行元素进行逻辑加,成为新的1、2、4行的元素。 1 0 1 0 0 1 1 1 0...
  • 根据每头牛之间的关系生成一张图, Warshall算法得到传递闭包。 若一头牛与其它每头牛之间关系确定, 则这头牛的排名就确定。 #include #include #include #include #include #define N 110 #...
  • #include main() {  int i,n,j,k,a,b,x[100][100];  while(scanf("%d",&n)!=EOF)  {  for(i=1;i  for(j=1;j  scanf("%d",&x[i][j]);  for(i=1;i  for(j=1;j  for(k=1;... x[j][k]=x

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,000
精华内容 400
关键字:

warshall算法求闭包