设无向图以邻接矩阵表示,设计算法求该无向图中边的数目
时间: 2023-11-18 22:11:54 浏览: 149
假设邻接矩阵为 $A$,那么该无向图中边的数目就是邻接矩阵 $A$ 中非零元素的个数除以 $2$。
具体实现可以遍历邻接矩阵 $A$,统计非零元素的个数,然后除以 $2$ 即可得到边的数目。以下是 Python 代码示例:
```python
def edge_count(adj_matrix):
count = 0
n = len(adj_matrix)
for i in range(n):
for j in range(i+1, n):
if adj_matrix[i][j] != 0:
count += 1
return count
```
其中 `adj_matrix` 是邻接矩阵,`n` 是矩阵的大小,遍历时只需遍历矩阵的上三角即可。最后返回的 `count` 就是边的数目。
阅读全文