Fermeture Transitive d’un Graphe (传递闭包)

图的传递闭包（Transitive Closure） 主要用于描述图中**可达性（reachability）**的关系。

给定一个有向图 G = (V, E) ，其传递闭包 G* 是一个新的图，其中：
若 从顶点 u 可以通过某条路径到达 v，那么在 G* 中， (u, v) 之间直接有一条边。即：若 u 能通过 1 条或多条边到达 v ，则在传递闭包中直接连接 u 和 v。

Warshall算法

Warshall 算法简介

算法概述

Warshall 算法用于计算有向图的传递闭包，即判断图中哪些顶点是可达的。它是 Floyd-Warshall 算法 的一种特例，专门用于可达性问题。

算法思想

对于一个有向图的 邻接矩阵 A，如果存在路径 从顶点 i 到 j，则在 传递闭包矩阵 T 中，T[i][j] 置为 1。
算法通过动态规划逐步更新可达性信息。

算法步骤

  1. 初始化：将原始邻接矩阵 A 作为可达性矩阵 T。

  2. 逐步加入中间点 k：

    • 如果从 i 到 k 可达，且从 k 到 j 可达，那么 i 到 j 也可达，即：
      T[i][j] = T[i][j] || (T[i][k] && T[k][j])

  3. 重复步骤 2 直到所有可能的中间点都被考虑。

做题步骤

讲人话就是：

  1. 圈出第一行和第一列
  2. 找出第一列中不为0（为1）的元素所在的行
  3. 把这些行和第一行做或运算，得到新的行
  4. 重复以上步骤，继续第二行第二列…
f1

可以参考一下哔站up村里一支_花的视频

https://www.bilibili.com/video/BV1u24y1F7pd?spm_id_from=333.788.recommend_more_video.-1&vd_source=45ab723bde86c3c74f1b89623e55e075

*还有一种算法也可以参考：https://www.bilibili.com/video/BV1Us421w7Yz/?spm_id_from=333.337.search-card.all.click&vd_source=45ab723bde86c3c74f1b89623e55e075

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Procédure FermetureTransitive(G, M*)
Début
    //Initialisation M⁰ = MAdj + Identité
    Pour s variant de 1 à n faire
        Pour t variant de 1 à n faire
            Si (s, t) appartient à A alors
                M⁽⁰⁾[s][t] ← 1
            Sinon
                M⁽⁰⁾[s][t] ← 1
            Finsi
        FfinPour
        M⁽⁰⁾[s][s] ← 1
    FfinPour
    //Itérations : mₛₜ⁽ᵏ⁾ = mₛₜ⁽ᵏ⁻¹⁾ ∪ (mₛₖ⁽ᵏ⁻¹⁾ ∩ mₖₜ⁽ᵏ⁻¹⁾)
    Pour k variant de 1 à n faire
        Pour s variant de 1 à n faire
            Pour t variant de 1 à n faire
                M⁽ᵏ⁾[s][t] ← M⁽ᵏ⁻¹⁾[s][t] ∪ (M⁽ᵏ⁻¹⁾[s][k] ∩ M⁽ᵏ⁻¹⁾[k][t])
            FfinPour
        FfinPour
    FfinPour
Fin

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 计算图的传递闭包的函数
// 参数：g 是一个表示图的邻接矩阵的结构体，M 是用于存储计算得到的传递闭包矩阵的二维数组
void FermetureTransitive_commentaire(MatAdj g, int **M) {
    // 初始化传递闭包矩阵 M，根据图 g 的邻接矩阵来设置初始值
    for (int s = 0; s < g.nbSom; s++) {
        for (int t = 0; t < g.nbSom; t++) {
            // 如果图 g 的邻接矩阵中 s 到 t 有边（值为 1）
            if (g.mat[s][t] == 1) {
                // 则在传递闭包矩阵 M 中设置 s 到 t 可达（值为 1）
                M[s][t] = 1;
            } else {
                // 否则在传递闭包矩阵 M 中设置 s 到 t 不可达（值为 0）
                M[s][t] = 0;
            }
        }
        // 每个顶点自身到自身是可达的，所以将 M[s][s] 设置为 1
        M[s][s] = 1;
    }

    // 利用 Floyd-Warshall 算法的思想来计算传递闭包
    // 这里通过中间顶点 k 来判断是否存在从 s 到 t 的路径
    for (int k = 0; k < g.nbSom; k++) {
        for (int s = 0; s < g.nbSom; s++) {
            for (int t = 0; t < g.nbSom; t++) {
                // 如果当前 M[s][t] 为 1（即已经知道 s 到 t 可达），或者存在从 s 到 k 且从 k 到 t 的路径
                M[s][t] = M[s][t] || (M[s][k] && M[k][t]);
                // 则更新 M[s][t] 为 1，表示 s 到 t 可达
            }
        }
    }
}

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<stdlib.h>
#include<stdio.h>
#include "FermetureTransitive.h"

int **allocM(MatAdj g) {
    // 为传递闭包矩阵分配内存

    int **M = (int **) malloc(g.nbSom * sizeof(int *));
    for (int i = 0; i < g.nbSom; i++) {
        M[i] = (int *) malloc(g.nbSom * sizeof(int));
    }

    return M;
}

void printFermeture(int n, int **M) {
    // 输出传递闭包矩阵
    printf("传递闭包矩阵:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", M[i][j]);
        }
        printf("\n");
    }
}


int main() {
    int n = 3;
    MatAdj ma;
    ma.nbSom = n;
    ma.mat = (int **) malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        ma.mat[i] = (int *) malloc(n * sizeof(int));
    }

    // 初始化矩阵（有向图不带自环）
    int adj[3][3] = {
        {0, 1, 0},
        {0, 0, 0},
        {0, 0, 0}
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ma.mat[i][j] = adj[i][j];
        }
    }

    int **M = allocM(ma);

    // 调用计算传递闭包的函数
    FermetureTransitive(ma, M);

    //打印 M
    printFermeture(n,M);

    // 释放邻接矩阵和传递闭包矩阵的内存
    for (int i = 0; i < ma.nbSom; i++) {
        free(ma.mat[i]);
        free(M[i]);
    }
    free(ma.mat);
    free(M);
}

//结果
传递闭包矩阵:
1 1 0 
0 1 0 
0 0 1