数据结构若有向图采用邻接表作为存储结构,试给出计算图中各顶点的入度的算法。c++
时间: 2024-05-11 10:20:05 浏览: 187
图的邻接矩阵和邻接表存储结构(C++)
可以遍历整个邻接表,统计每个顶点被指向的次数,即可得到该顶点的入度。具体实现如下:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000;
vector<int> graph[MAXN]; // 邻接表存储结构
int indegree[MAXN]; // 存储每个顶点的入度
void calc_indegree(int n) {
// 初始化每个顶点的入度为0
for (int i = 0; i < n; i++) {
indegree[i] = 0;
}
// 遍历整个邻接表,统计每个顶点的入度
for (int i = 0; i < n; i++) {
for (int j = 0; j < graph[i].size(); j++) {
int v = graph[i][j];
indegree[v]++;
}
}
}
int main() {
// 读入图的信息
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
// 计算每个顶点的入度
calc_indegree(n);
// 输出每个顶点的入度
for (int i = 0; i < n; i++) {
cout << "Vertex " << i << " indegree: " << indegree[i] << endl;
}
return 0;
}
```
阅读全文