创建一个无向图,选用任一数据存储结构,并求出任意一个项的度
时间: 2024-01-11 07:03:57 浏览: 98
好的,我可以帮你解答这个问题。首先,无向图可以使用邻接表或邻接矩阵两种数据结构进行存储。其中,邻接表适用于稀疏图,而邻接矩阵适用于稠密图。
我这里以邻接表为例,假设我们要创建以下这个无向图:
```
1---2
| |
3---4---5
```
我们可以使用一个包含五个链表的数组来存储这个图,每个链表表示一个顶点的邻居节点。具体实现如下:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, v1, v2):
self.adj_list[v1].append(v2)
self.adj_list[v2].append(v1)
def get_degree(self, v):
return len(self.adj_list[v])
```
然后我们可以用以下代码来创建这个图,并求出顶点4的度:
```python
g = Graph(5)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(4, 5)
print(g.get_degree(4)) # 输出 3
```
这里的 `get_degree` 方法可以根据顶点的编号返回该顶点的度。在上面的例子中,顶点4的邻居节点为2、3和5,因此它的度为3。
阅读全文