1. 实验目的

熟悉 Warshall 算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。

2. 实验内容

定义 1：设 $R$ 是 $A$ 上的二元关系，$R$ 的自反（对称、传递）闭包是关系 $R_1$，则：

1. $R_1$ 是自反的（对称的、传递的）
2. $R \subseteq R_1$
3. 对任何自反的（对称的、传递的）关系 $R_2$，若 $R \subseteq R_2$，则 $R_1 \subseteq R_2$

$R$ 的自反、对称和传递闭包分别记为 $r(R)$、$s(R)$ 和 $t(R)$。

定理 1：令 $R \subseteq A \times A$，则：

1. $r(R) = R \cup I_A$
2. $s(R) = R \cup R^{-1}$
3. $t(R) = R \cup R^2 \cup R^3 \cup \cdots$

Warshall 算法：设 $R$ 是 $n$ 个元素集合 $A$ 上的二元关系，$M$ 是 $R$ 的关系矩阵，其求传递闭包的过程如下：

1. 置新矩阵 A := M
2. 置 i := 1
3. for j = 1 to n do
   if A[j, i] = 1 then do
   for k = 1 to n do
   A[j, k] := A[j, k] + A[i, k]
4. i := i + 1
5. if i ≤ n then 转步骤 3，否则停止

本实验要求：

1. 从键盘输入图的邻接矩阵和一正整数 $m$，计算结点两两之间长度为 $m$ 的路的数目，考虑有向图和无向图
2. 从键盘输入一个关系的关系矩阵，计算其自反闭包、对称闭包和传递闭包，计算传递闭包时使用 Warshall 算法
3. 用 C 语言、C++ 或 Python 实现

3. 程序清单

▶

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LINE_BUF 512  // 单行输入缓冲大小

/**
 * @brief 从一行文本中读取并校验 n 个 0/1 元素到 row 数组
 *
 * @param n 元素数量
 * @param row 数组指针
 * @return int X->读取元素个数 | -1->输入结束
 */
static int read_row(int n, int *row)
{
    char buf[LINE_BUF];

    if (fgets(buf, LINE_BUF, stdin) == NULL) {
        // 输入已结束
        return -1;
    }

    int   cnt = 0;
    char *tok = strtok(buf, " \t\r\n");
    while (tok != NULL) {
        // 一行中的元素个数超过 n 时按输入有误处理, 避免越界写入
        if (cnt >= n) {
            return n + 1;
        }

        char *end = NULL;
        long  v   = strtol(tok, &end, 10);
        // 只接受整数, 且取值只能是 0 或 1
        if (end == tok || *end != '\0' || (v != 0 && v != 1)) {
            return cnt;
        }

        row[cnt++] = (int)v;
        tok        = strtok(NULL, " \t\r\n");
    }
    return cnt;
}

/**
 * @brief 为 n 阶方阵分配内存
 *
 * @param n 矩阵阶数
 * @return int** 矩阵二阶数组指针
 */
static int **alloc_matrix(int n)
{
    // 为指针数组(每行首地址)分配内存
    int **matrix = (int **)malloc(n * sizeof(int *));
    if (matrix == NULL) {
        printf("Failed to allocate array memory.\r\n");
        exit(1);
    }

    for (int i = 0; i < n; i++) {
        // 为每一行元素分配内存
        matrix[i] = (int *)malloc(n * sizeof(int));
        if (matrix[i] == NULL) {
            printf("Failed to allocate elements memory.\r\n");
            // 释放已分配的各行及指针数组后再退出
            for (int j = 0; j < i; j++) {
                free(matrix[j]);
            }
            free(matrix);
            exit(1);
        }
    }
    return matrix;
}

/**
 * @brief 释放 n 阶方阵占用的内存
 *
 * @param n 矩阵阶数
 * @param matrix 矩阵二阶数组指针
 */
static void free_matrix(int n, int **matrix)
{
    for (int i = 0; i < n; i++) {
        free(matrix[i]);
    }
    free(matrix);
}

/**
 * @brief 深拷贝一份 n 阶方阵
 *
 * @param n 矩阵阶数
 * @param src 源矩阵二阶数组指针
 * @return int** 拷贝出的新矩阵
 */
static int **copy_matrix(int n, int **src)
{
    int **dst = alloc_matrix(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dst[i][j] = src[i][j];
        }
    }
    return dst;
}

/**
 * @brief 输出 n 阶方阵
 *
 * @param n 矩阵阶数
 * @param matrix 矩阵二阶数组指针
 */
static void display_matrix(int n, int **matrix)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\r\n");
    }
}

/**
 * @brief 从键盘获取 n 阶 0/1 关系矩阵的函数, 按行输入
 *
 * @param n 矩阵阶数
 * @return int** 矩阵二阶数组指针
 */
int **get_matrix(int n)
{
    // 逐行输入并校验, 直到每行都合法
    int **matrix = alloc_matrix(n);
    for (int i = 0; i < n; i++) {
        while (1) {
            int cnt = read_row(n, matrix[i]);
            if (cnt == n) {
                // 本行读取成功
                break;
            }
            if (cnt == -1) {
                printf("Illegal input!\r\n");
                exit(1);
            }
            printf("第 %d 行输入有误，应为 %d 个 0 或 1，请重新输入：\r\n", i + 1, n);
        }
    }
    return matrix;
}

/**
 * @brief 计算关系矩阵的自反闭包(主对角线上补 1)
 *
 * @param n 矩阵阶数
 * @param matrix 原关系矩阵二阶数组指针
 * @return int** 自反闭包矩阵, 由调用方释放
 */
int **reflexive_closure(int n, int **matrix)
{
    int **a = copy_matrix(n, matrix);
    for (int i = 0; i < n; i++) {
        a[i][i] = 1;
    }
    return a;
}

/**
 * @brief 计算关系矩阵的对称闭包(对称位置补 1)
 *
 * @param n 矩阵阶数
 * @param matrix 原关系矩阵二阶数组指针
 * @return int** 对称闭包矩阵, 由调用方释放
 */
int **symmetric_closure(int n, int **matrix)
{
    int **a = copy_matrix(n, matrix);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // i 与 j 之间只要有方向, 就把两个方向都补成 1
            if (a[i][j] == 1 || a[j][i] == 1) {
                a[i][j] = 1;
                a[j][i] = 1;
            }
        }
    }
    return a;
}

/**
 * @brief 用 Warshall 算法计算关系矩阵的传递闭包
 * 外层依次以第 k 个顶点作为"中转顶点"：
 * 若 i 能直接到达 k, 则把 k 能到达的所有 j 也并入 i 的可达集.
 *
 * @param n 矩阵阶数
 * @param matrix 原关系矩阵二阶数组指针
 * @return int** 传递闭包矩阵, 由调用方释放
 */
int **transitive_closure(int n, int **matrix)
{
    int **a = copy_matrix(n, matrix);

    for (int k = 0; k < n; k++) {              // 中转顶点
        for (int i = 0; i < n; i++) {          // 起点
            if (a[i][k] == 1) {                // i 能到达 k
                for (int j = 0; j < n; j++) {  // 终点
                    // 合并第 k 行的可达关系到第 i 行
                    a[i][j] = a[i][j] || a[k][j];
                }
            }
        }
    }
    return a;
}

int main(void)
{
    int n = 0;
    printf("请输入矩阵的阶数 n：");
    if (scanf("%d", &n) != 1) {
        printf("阶数输入错误！\r\n");
        return 1;
    }

    if (n <= 0 || n > 100) {
        printf("阶数 n 应为 1 ~ 100 之间的整数！\r\n");
        return 1;
    }

    // 吃掉阶数后的换行符, 避免残留影响后续逐行读取
    int ch;
    while ((ch = getchar()) != '\n' && ch != EOF) {
    }

    // 逐行输入 0/1 关系矩阵
    printf("请按行输入关系矩阵，使用空格分隔（元素为 0 或 1）：\r\n");
    int **matrix = get_matrix(n);

    // 计算三种闭包
    int **reflexive  = reflexive_closure(n, matrix);
    int **symmetric  = symmetric_closure(n, matrix);
    int **transitive = transitive_closure(n, matrix);

    printf("关系矩阵的自反闭包是：\r\n");
    display_matrix(n, reflexive);

    printf("关系矩阵的对称闭包是：\r\n");
    display_matrix(n, symmetric);

    printf("关系矩阵的传递闭包是（Warshall 算法）：\r\n");
    display_matrix(n, transitive);

    // 释放内存
    free_matrix(n, transitive);
    free_matrix(n, symmetric);
    free_matrix(n, reflexive);
    free_matrix(n, matrix);
    return 0;
}

4. 调试步骤

1. 输入测试数据：

请输入矩阵的阶数 n：3
请按行输入关系矩阵，使用空格分隔（元素为 0 或 1）：
1 0 1
0 0 0
0 1 0

2. 程序输出：

关系矩阵的自反闭包是：
1 0 1 
0 1 0 
0 1 1 
关系矩阵的对称闭包是：
1 0 1 
0 0 1 
1 1 0 
关系矩阵的传递闭包是（Warshall 算法）：
1 1 1 
0 0 0 
0 1 0

5. 分析与思考

该程序的难点在于二维数组的传递，如何在向函数中传入二维数组的指针的同时在函数中动态建立一个二维数组，以防止对手动输入的数组进行更改。同时使得函数返回计算得到的二维数组的指针。