离散数学道路矩阵的Warshall算法编程代码

道路矩阵的Warshall算法，判别连通性的算法，二叉树的遍历，最小生成树的Kruskal算法

img

引用chatGPT作答，道路矩阵的Warshall算法：

Warshall算法是一种用于求解图的传递闭包的算法，其核心思想是动态规划。给定一个有向图$G=(V,E)$，其传递闭包定义为$G^=(V,E^)$，其中$E^$是满足对于所有的$u,v\in V$，$u$可到达$v$当且仅当$(u,v)\in E^$。算法的实现步骤如下：

1.初始化传递闭包矩阵$T$为道路矩阵$M$。
2.对于每个节点$k\in V$，依次更新矩阵$T$中每一对节点$(i,j)$的值：
如果存在一条从节点$i$到节点$j$并且从节点$i$到节点$k$，从节点$k$到节点$j$都存在路径，则将$T(i,j)$设置为1。
3.返回传递闭包矩阵$T$。

以下是使用C语言实现Warshall算法的代码：

#include <stdio.h>
#define MAXSIZE 100

void warshall_algorithm(int M[][MAXSIZE], int n) {
    int T[MAXSIZE][MAXSIZE];
    int i, j, k;

    // 初始化传递闭包矩阵为道路矩阵
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            T[i][j] = M[i][j];
        }
    }

    // 对每个节点k，更新每一对节点(i,j)的值
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                T[i][j] = T[i][j] || (T[i][k] && T[k][j]);
            }
        }
    }

    // 输出传递闭包矩阵
    printf("Transitive closure matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", T[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int M[MAXSIZE][MAXSIZE];
    int n, i, j;

    // 读入道路矩阵的大小和元素值
    printf("Enter the size of road matrix: ");
    scanf("%d", &n);
    printf("Enter the elements of road matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &M[i][j]);
        }
    }

    // 调用Warshall算法
    warshall_algorithm(M, n);

    return 0;
}

在这个实现中，我们首先定义了一个warshall_algorithm函数来执行Warshall算法。该函数需要两个参数：一个表示道路矩阵的二维数组M和矩阵的大小n。在函数中，我们首先创建一个二维数组T，并将其初始化为道路矩阵。然后，我们使用三重循环依次更新矩阵T中的每一对节点的值。最后，我们输出传递闭包矩阵。

在main函数中，我们首先读入道路矩阵的大小和元素值，然后调用warshall_algorithm函数执行Warshall算法。

  • 请看👉 ：动态规划之有向图传递闭包的计算warshall算法图解详
  • 除此之外, 这篇博客: 离散数学中的warshall算法应用中的 传递闭包 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  • #include<stdio.h>
#include<string.h>
int a[110][110];

void warshell(int n)
{

    int k, i, j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(a[j][i])
            {
                for(k=1; k<=n; k++)
                {
                    a[j][k] = a[j][k] + a[i][k];
                    if(a[j][k] >= 1)
                        a[j][k] = 1;
                }
            }
        }
    }
}
int main()
{
    int m, n, x, y, i, j, ans, flag[110];
    while(~scanf("%d %d", &n, &m))
    {
        ans = 0;
        memset(a, 0, sizeof(a));
        memset(flag, 1, sizeof(flag));
        while(m--)
        {
            scanf("%d %d", &x, &y);
            a[x][y] = 1;
        }
        warshell(n);
        for(j=1; j<=n; j++)
        {

            for(i=1; i<=n; i++)
            {
                if(i == j)
                {
                    if(a[i][j])
                    {
                        flag[j] = 0;
                        break;
                    }
                }
                else if(!a[i][j])
                {
                    if(!a[j][i])
                    {
                        flag[j] = 0;
                        break;
                    }
                }
            }
            if(flag[j])
            {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}