写一个算法求图中每个节点的度
时间: 2023-12-06 13:44:17 浏览: 73
假设我们用邻接矩阵表示图,那么求每个节点的度可以采用以下算法:
1. 初始化一个长度为节点数的数组degree,用于存储每个节点的度数,初始值全部为0。
2. 遍历邻接矩阵,对于每个节点i,统计与其相连的边数,即邻接矩阵中第i行所有非零元素的个数,将其赋值给degree[i]。
3. 遍历完成后,degree数组中第i个元素即为图中第i个节点的度数。
以下是Python代码实现:
```python
def get_degree(adj_matrix):
n = len(adj_matrix)
degree = [0] * n
for i in range(n):
for j in range(n):
if adj_matrix[i][j] != 0:
degree[i] += 1
return degree
```
其中,adj_matrix是一个n*n的邻接矩阵。
相关问题
写一个算法求有向图中每个节点的度数
可以通过遍历有向图中每个节点的出边或入边来计算每个节点的出度或入度,最终将两者相加得到每个节点的总度数。
以下是一个示例代码,假设有向图用邻接表存储:
```
// 计算有向图中每个节点的度数
void calculateDegrees(vector<vector<int>>& graph, vector<int>& inDegrees, vector<int>& outDegrees) {
int n = graph.size();
for (int i = 0; i < n; i++) {
outDegrees[i] = graph[i].size(); // 计算出度
for (int j : graph[i]) {
inDegrees[j]++; // 计算入度
}
}
for (int i = 0; i < n; i++) {
outDegrees[i] += inDegrees[i]; // 计算总度数
}
}
```
其中,`graph` 是邻接表,`inDegrees` 是每个节点的入度数组,`outDegrees` 是每个节点的出度数组。函数先遍历每个节点的出边计算出度,再遍历每个节点的入边计算入度,最后将出度和入度相加得到总度数。
写一个算法求图的度
假设给定一个无向图,我们可以通过以下算法求出每个节点的度数:
1. 创建一个大小为 $n$ 的数组 $degree$,其中 $n$ 为图中节点的数量。
2. 遍历图中的每条边,对于边 $(u, v)$,将 $degree[u]$ 和 $degree[v]$ 分别增加 1。
3. 遍历完所有的边后,$degree[i]$ 的值就是节点 $i$ 的度数。
以下是该算法的 Python 代码实现:
```
def degree_of_graph(n, edges):
degree = [0] * n
for u, v in edges:
degree[u] += 1
degree[v] += 1
return degree
```
其中,$n$ 表示图中节点的数量,$edges$ 是一个包含所有边的列表。函数返回一个长度为 $n$ 的列表,列表中每个元素表示对应节点的度数。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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)