图 G 是一个有向简单图,矩阵 B 是其邻接矩阵,请问如何算出每个点的度数。如何算出一个图的边数。
时间: 2024-01-24 08:19:06 浏览: 22
对于有向图 G 的邻接矩阵 B,第 i 行第 j 列的元素表示从点 i 到点 j 的有向边的权重或者存在情况。对于一个点 i 的度数,可以先求出第 i 行的和,即为其出度;再求出第 i 列的和,即为其入度。点 i 的度数为出度与入度之和。
具体的计算方法为:设 G 有 n 个点,则对于点 i,其度数为:
$deg(i)=\sum_{j=1}^{n}b_{i,j}+\sum_{j=1}^{n}b_{j,i}$
其中,$b_{i,j}$ 表示第 i 行第 j 列的元素,$b_{j,i}$ 表示第 j 行第 i 列的元素。
对于一个有向图,边数为所有点的出度之和,也即所有点度数之和,即:
$E=\sum_{i=1}^{n}deg(i)$
相关问题
用js输入有向图的邻接矩阵输出每个顶点的输入和输出度数
下面是一个实现该功能的 JavaScript 代码:
```javascript
// 输入有向图的邻接矩阵
var matrix = [
[0, 1, 0, 0],
[0, 0, 1, 1],
[0, 0, 0, 1],
[1, 0, 0, 0]
];
// 计算每个顶点的输入和输出度数
var inDegrees = [];
var outDegrees = [];
for (var i = 0; i < matrix.length; i++) {
var inDegree = 0;
var outDegree = 0;
for (var j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] === 1) {
outDegree++;
}
if (matrix[j][i] === 1) {
inDegree++;
}
}
inDegrees.push(inDegree);
outDegrees.push(outDegree);
}
// 输出每个顶点的输入和输出度数
for (var i = 0; i < inDegrees.length; i++) {
console.log("顶点 " + i + " 的输入度数为 " + inDegrees[i] + ",输出度数为 " + outDegrees[i]);
}
```
在这个例子中,输入的邻接矩阵表示了一个包含 4 个顶点的有向图,每个顶点的输入和输出度数将会被计算并输出到控制台。
有向图邻接矩阵建图和度数输出
以下是有向图邻接矩阵建图和度数输出的示例代码:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, start_vertex, end_vertex):
self.adj_matrix[start_vertex][end_vertex] = 1
def get_indegree(self, vertex):
indegree = 0
for i in range(self.num_vertices):
if self.adj_matrix[i][vertex] == 1:
indegree += 1
return indegree
def get_outdegree(self, vertex):
outdegree = 0
for i in range(self.num_vertices):
if self.adj_matrix[vertex][i] == 1:
outdegree += 1
return outdegree
# 创建一个有向图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2,3)
g.add_edge(3, 4)
# 输出每个顶点的入度和出度
for i in range(g.num_vertices):
print("Vertex", i)
print("Indegree:", g.get_indegree(i))
print("Outdegree:", g.get_outdegree(i))
print()
```
输出结果:
```
Vertex 0
Indegree: 0
Outdegree: 2
Vertex 1
Indegree: 1
Outdegree: 1
Vertex 2
Indegree: 1
Outdegree: 1
Vertex 3
Indegree: 2
Outdegree: 1
Vertex 4
Indegree: 1
Outdegree: 0
```
相关推荐
![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)