邻接矩阵表示法计算各个节点的度代码
时间: 2023-06-26 16:05:50 浏览: 170
假设邻接矩阵为 `adj_matrix`,节点数量为 `n`,可以使用以下代码计算每个节点的度:
```python
degree = [0] * n # 初始化每个节点的度为 0
for i in range(n):
for j in range(n):
if adj_matrix[i][j] == 1:
degree[i] += 1 # 节点 i 的度加 1
print(degree) # 输出每个节点的度
```
解释一下上面的代码:
- 我们首先初始化每个节点的度为 0,即 `degree = [0] * n`。
- 然后遍历邻接矩阵的每一个元素,如果发现 `adj_matrix[i][j] == 1`,说明节点 i 和节点 j 之间有一条边,因此节点 i 的度要加 1,即 `degree[i] += 1`。
- 最后输出每个节点的度,即 `print(degree)`。
相关问题
邻接矩阵表示法创建无向图 代码
下面是使用邻接矩阵表示法创建无向图的代码示例,其中使用了二维数组来存储邻接矩阵:
```c++
#include<iostream>
using namespace std;
const int MAXN = 100; // 图的最大节点数
int graph[MAXN][MAXN]; // 邻接矩阵表示法
int n, m; // n 表示节点数,m 表示边数
int main()
{
cin >> n >> m; // 输入节点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入一条边的两个端点
graph[u][v] = 1; // 标记有一条从 u 到 v 的边
graph[v][u] = 1; // 由于是无向图,所以还要标记有一条从 v 到 u 的边
}
return 0;
}
```
以上代码实现了使用邻接矩阵表示法创建无向图的功能,可以在输入节点数和边数后,逐个输入边的两个端点,然后标记对应的邻接矩阵元素。
有向图邻接矩阵表示法
有向图邻接矩阵表示法是一种常见的图的表示方法,它使用一个二维数组来表示有向图中各个节点之间的关系。
具体来说,如果有一个有向图 G=(V,E),其中 V={v1,v2,...,vn} 表示节点集合,E 表示边的集合,那么可以使用一个 n×n 的二维数组 A 来表示这个图,其中 A[i][j] 表示从节点 i 到节点 j 是否有一条边。如果有边,那么 A[i][j] 的值为 1;否则,A[i][j] 的值为 0。
更进一步地,如果有向图中的边有权重,那么可以将 A[i][j] 的值改为边的权重。
有向图邻接矩阵表示法的优点是可以快速地判断两个节点之间是否有边,时间复杂度为 O(1)。缺点是如果图比较稀疏,即节点数远大于边数,那么邻接矩阵会占用大量的空间,造成浪费。此外,邻接矩阵表示法也不适合表示带有环的图。