已知一个有向图的邻接表,试编写一个算法,计算各顶点的入度,写出一个完整c++代码给我
时间: 2024-01-24 19:04:40 浏览: 37
以下是一个基于邻接表的有向图计算各顶点入度的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m; // 输入顶点数和边数
vector<int> indegree(n, 0); // 初始化每个顶点的入度为0
vector<vector<int>> adjList(n); // 创建邻接表
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入边的起点和终点
adjList[u].push_back(v); // 将终点添加到起点的邻接表中
indegree[v]++; // 终点入度加1
}
// 输出每个顶点的入度
for (int i = 0; i < n; i++) {
cout << "Vertex " << i << " indegree: " << indegree[i] << endl;
}
return 0;
}
```
该算法的时间复杂度为O(m+n),其中m为边数,n为顶点数。
相关问题
已知有一个有向图的邻接表,试编写一个算法,计算各顶点的入度。的代码
假设邻接表中有 $n$ 个节点,我们可以使用一个长度为 $n$ 的数组来记录每个节点的入度。算法的具体步骤如下:
1. 初始化每个节点的入度为 0。
2. 遍历邻接表中的每个节点,对于每个节点的邻接链表中的每个节点,将其对应的节点的入度加 1。
3. 返回记录每个节点入度的数组。
下面是具体的实现代码:
```python
def compute_indegree(adj_list):
n = len(adj_list)
indegrees = [0] * n
for node in adj_list:
for neighbor in adj_list[node]:
indegrees[neighbor] += 1
return indegrees
```
其中 `adj_list` 是邻接表,它是一个字典,键为节点编号,值为一个列表,表示该节点的邻接链表。返回值 `indegrees` 是一个列表,表示每个节点的入度。
求邻接表表示的有向图各顶点的入度 正文:已知有一个有向图的邻接表,试编写一个算法,计算各顶点的入度。
算法步骤如下:
1. 初始化一个数组 inDegree,长度为顶点数,全部初始化为0。
2. 遍历邻接表,对于每个链表中的节点,将节点指向的顶点的入度加1,即:inDegree[v]++,其中 v 是节点指向的顶点。
3. 遍历 inDegree 数组,输出每个顶点的入度。
下面是 Python 代码实现:
```python
def calc_indegree(adj_list):
# 初始化入度数组
num_vertices = len(adj_list)
in_degree = [0] * num_vertices
# 遍历邻接表,计算入度
for edges in adj_list:
for v in edges:
in_degree[v] += 1
# 输出入度
for i in range(num_vertices):
print(f"Vertex {i} has in-degree {in_degree[i]}")
# 示例代码
adj_list = [[1, 2], [2], [3], [], [1, 2]]
calc_indegree(adj_list)
```
输出结果为:
```
Vertex 0 has in-degree 1
Vertex 1 has in-degree 1
Vertex 2 has in-degree 2
Vertex 3 has in-degree 1
Vertex 4 has in-degree 0
```
其中,邻接表表示的有向图如下所示:
```
0 -> 1 -> 2
1 -> 2
2 -> 3
3 ->
4 -> 1 -> 2
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)