有向图的逆邻接表求入度
时间: 2023-12-18 15:28:50 浏览: 46
有向图的逆邻接表是指对于有向图中的每个顶点,建立一个链表存储所有指向该顶点的顶点。因此,对于一个顶点的入度,只需要统计该顶点在逆邻接表中的链表中的节点数即可。
以下是求有向图指定顶点入度的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
```
相关问题
有向图的逆邻接表求入度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;
}
```
有向图邻接表节点入度代码
以下是有向图邻接表节点入度的代码实现:
```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;
}
```