有向图邻接表节点入度代码
时间: 2023-12-07 14:40:04 浏览: 47
以下是有向图邻接表节点入度的代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
struct Edge {
int v, nxt;
} e[MAXN];
int head[MAXN], inDegree[MAXN], cnt;
void addEdge(int u, int v) {
e[++cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int main() {
memset(head, -1, sizeof(head));
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
inDegree[v]++;
}
for (int i = 1; i <= n; i++) {
cout << "节点" << i << "的入度为:" << inDegree[i] << endl;
}
return 0;
}
```
相关问题
有向图的逆邻接表求入度
有向图的逆邻接表是指对于有向图中的每个顶点,建立一个链表存储所有指向该顶点的顶点。因此,对于一个顶点的入度,只需要统计该顶点在逆邻接表中的链表中的节点数即可。
以下是求有向图指定顶点入度的Python代码示例,其中graph为有向图的邻接表表示,vertex为指定的顶点:
```python
def get_indegree(graph, vertex):
if vertex not in graph:
return -1
indegree = 0
for node in graph:
for neighbor in graph[node]:
if neighbor == vertex:
indegree += 1
return indegree
```
建立一个逆邻接表计算入度
逆邻接表是一种表示有向图的数据结构,它记录了每个节点的入边。因此,我们可以通过逆邻接表计算每个节点的入度。
具体实现如下:
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
```