实现图的邻接矩阵存储结构,并实现图的创建和计算项点的度操作。
时间: 2024-02-01 16:15:19 浏览: 4
实现邻接矩阵存储结构的图,需要用一个二维数组来表示。假设有 $n$ 个顶点,那么二维数组的大小就是 $n\times n$。
在这个二维数组中,如果第 $i$ 个顶点和第 $j$ 个顶点之间有一条边,则数组中第 $i$ 行第 $j$ 列的值为 1;如果没有边,则值为 0。
以下是 Python 代码实现:
```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, i, j):
self.adj_matrix[i][j] = 1
self.adj_matrix[j][i] = 1
def get_degree(self, i):
degree = 0
for j in range(self.num_vertices):
degree += self.adj_matrix[i][j]
return degree
```
在上面的代码中,我们定义了一个 `Graph` 类,它有两个成员变量:`num_vertices` 表示图中的顶点数,`adj_matrix` 表示邻接矩阵。
类中的 `add_edge` 方法用来添加边,它把 `adj_matrix[i][j]` 和 `adj_matrix[j][i]` 的值都设为 1,表示第 $i$ 个顶点和第 $j$ 个顶点之间有一条边。
类中的 `get_degree` 方法用来计算顶点的度数,它遍历第 $i$ 行中所有的元素,如果值为 1,则表示第 $i$ 个顶点和该行对应的顶点之间有一条边,因此它的度数加 1。最后返回度数即可。
下面是测试代码:
```python
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(5):
print(f"Vertex {i} has degree {g.get_degree(i)}")
```
输出:
```
Vertex 0 has degree 2
Vertex 1 has degree 2
Vertex 2 has degree 2
Vertex 3 has degree 3
Vertex 4 has degree 1
```