有向图的表示及可达矩阵的计算

有向图可以用邻接矩阵或邻接表来表示。其中，邻接矩阵是一个二维数组，数组的第i行第j列表示从节点i到节点j是否有一条有向边；邻接表则是一个由链表组成的数组，数组的第i个链表表示从节点i出发的所有有向边的终点。

可达矩阵可以通过邻接矩阵来计算。可达矩阵是一个二维数组，数组的第i行第j列表示从节点i到节点j是否存在一条路径。可达矩阵可以通过邻接矩阵的幂运算来计算。假设邻接矩阵为A，可达矩阵为R，则R的第i行第j列为A的第i行与R的第j列对应位置的元素相乘再求和，即：

R[i][j] = A[i][0]*R[0][j] + A[i][1]*R[1][j] + ... + A[i][n-1]*R[n-1][j]

其中，n为节点数，A[i][k]表示从节点i到节点k是否有一条有向边。初始时，R等于A的一个副本。不断进行幂运算，直到R不再发生变化为止，此时R就是可达矩阵。

相关问题

有向图的表示和可达矩阵的计算

有向图可以用邻接矩阵或邻接表进行表示。其中邻接矩阵是一个二维矩阵，矩阵中的每一个元素表示从一个节点到另一个节点是否有一条有向边。如果有，则该元素为1，否则为0。邻接表则是一个数组，每个数组元素对应一个节点，该元素存储了该节点所有的出边信息。

可达矩阵是指一个矩阵，矩阵中的元素表示从一个节点到另一个节点是否存在一条路径。如果存在，则该元素为1，否则为0。可达矩阵的计算可以通过邻接矩阵进行转移，具体的计算方法为：初始化可达矩阵为邻接矩阵，然后对于每一对节点i和j，如果节点i能够到达节点j，则将可达矩阵中的(i, j)元素设为1，否则为0。这个过程可以通过Floyd算法或Warshall算法来实现。需要注意的是，如果图中存在环，则可达矩阵中的元素可能会出现循环依赖的情况，因此需要对环进行处理或者使用其他的算法来计算可达矩阵。

有向图的表示和可达矩阵的计算c++

以下是使用邻接矩阵表示有向图并计算可达矩阵的C++代码：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 100; // 最大节点数

int n; // 节点数
int g[MAXN][MAXN]; // 邻接矩阵
int reach[MAXN][MAXN]; // 可达矩阵

// 计算可达矩阵
void calc_reach() {
    memcpy(reach, g, sizeof(g)); // 初始化可达矩阵为邻接矩阵

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }
}

int main() {
    cin >> n;

    // 读入有向图
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    calc_reach(); // 计算可达矩阵

    // 输出可达矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << reach[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

该代码中，我们首先读入有向图，并使用邻接矩阵表示。然后，我们调用`calc_reach()`函数计算可达矩阵。在`calc_reach()`函数中，我们使用Floyd算法来计算可达矩阵。最后，我们输出可达矩阵。