有向图的表示和可达矩阵的计算c++
时间: 2024-02-17 07:02:22 浏览: 20
以下是使用邻接矩阵表示有向图并计算可达矩阵的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算法来计算可达矩阵。最后,我们输出可达矩阵。