有向图的邻接表存储,并计算给定结点的入度
时间: 2024-03-20 17:39:31 浏览: 59
好的,关于有向图的邻接表存储,我们可以使用一个数组来存储图中的所有节点,数组中的每个元素都是一个链表,链表中存储了该节点所指向的其他节点。如下是示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 10005; // 最大节点数
// 存储图的结构体
struct Graph {
int to; // 边指向的节点
int next; // 下一条边的编号
} edge[MAXN];
int head[MAXN]; // 存储每个节点的第一条边的编号
int cnt = 0; // 记录边的数量
// 添加一条从u到v的边
void addEdge(int u, int v) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
int main() {
int n, m; // n表示节点数量,m表示边数量
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v); // 添加一条从u到v的边
}
// 计算每个节点的入度
vector<int> inDegree(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = head[i]; j; j = edge[j].next) {
inDegree[edge[j].to]++;
}
}
// 输出每个节点的入度
for (int i = 1; i <= n; i++) {
cout << "节点 " << i << " 的入度为:" << inDegree[i] << endl;
}
return 0;
}
```
以上是一个简单的使用邻接表存储有向图,并计算节点入度的示例代码。
阅读全文
相关推荐


















