逆邻接表计算入度
时间: 2023-08-09 22:06:12 浏览: 79
逆邻接表是指对于每个节点,存储它的所有入边的信息。因此,可以通过遍历整个逆邻接表来计算每个节点的入度。
具体地,可以使用一个长度为节点数的数组,数组的下标表示节点编号,数组中的元素表示该节点的入度。遍历逆邻接表中的每个节点,对应节点的入度加一。
伪代码如下:
```
// 初始化数组,所有节点的入度均为0
for i in range(1, n+1):
indegree[i] = 0
// 遍历逆邻接表
for node in reverse_adjacency_list:
for edge in node.in_edges:
indegree[edge.end] += 1
```
其中,`n` 表示节点数,`reverse_adjacency_list` 表示逆邻接表。遍历逆邻接表时,可以直接对每个节点的入度进行累加,不必遍历所有入边。
相关问题
建立一个逆邻接表计算入度
逆邻接表是一种表示有向图的数据结构,它记录了每个节点的入边。因此,我们可以通过逆邻接表计算每个节点的入度。
具体实现如下:
1. 定义一个大小为n的数组indegree,其中n为节点总数,用于记录每个节点的入度。
2. 对于每个节点i,遍历它的所有邻居节点j,将indegree[j]的值加1。
3. 遍历indegree数组,输出每个节点的入度。
下面是C++的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 5; // 节点总数
vector<vector<int>> adjList = {{1, 2}, {3}, {3, 4}, {4}, {}}; // 邻接表表示的有向图
vector<int> indegree(n, 0); // 入度数组
// 遍历邻接表,更新入度数组
for (int i = 0; i < n; i++) {
for (int j : adjList[i]) {
indegree[j]++;
}
}
// 输出每个节点的入度
for (int i = 0; i < n; i++) {
cout << "Node " << i << " has indegree " << indegree[i] << endl;
}
return 0;
}
```
输出结果为:
```
Node 0 has indegree 0
Node 1 has indegree 1
Node 2 has indegree 1
Node 3 has indegree 2
Node 4 has indegree 2
```
其中,adjList表示的有向图为:
```
0 -> 1 -> 3 -> 4
-> 2 -> 3 -> 4
```
有向图的逆邻接表求入度c++
以下是C++中使用逆邻接表求有向图入度的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005;
vector<int> G[MAXN]; // 邻接表
vector<int> rG[MAXN]; // 逆邻接表
int in[MAXN]; // 入度
int main() {
int n, m;
cin >> n >> m; // 输入点数和边数
// 构建邻接表和逆邻接表
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
rG[v].push_back(u);
}
// 计算入度
for (int i = 1; i <= n; i++) {
for (int j = 0; j < rG[i].size(); j++) {
int v = rG[i][j];
in[i]++;
}
}
// 输出每个点的入度
for (int i = 1; i <= n; i++) {
cout << "入度[" << i << "] = " << in[i] << endl;
}
return 0;
}
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)