创建一个无向图,选用任一数据存储结构,并求出任意一个顶的度。请用代码实现
时间: 2023-08-25 18:04:28 浏览: 41
好的,我理解了你的问题。我可以使用邻接表来存储无向图,并且可以使用Python语言来实现。
首先,我们需要定义一个类来表示图中的每个节点。每个节点都需要存储它的值和与它相邻的节点列表。我们可以使用一个Python列表来存储这个列表。下面是代码:
```
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
```
接下来,我们可以定义一个类来表示整个图。这个类包含一个字典,其中键是每个节点的值,值是对应的节点对象。这样,我们就可以通过节点的值来访问它。下面是代码:
```
class Graph:
def __init__(self):
self.nodes = {}
def add_node(self, val):
node = Node(val)
self.nodes[val] = node
return node
def add_edge(self, val1, val2):
node1 = self.nodes[val1]
node2 = self.nodes[val2]
node1.neighbors.append(node2)
node2.neighbors.append(node1)
```
以上代码实现了添加节点和添加边的功能。现在,我们可以创建一个无向图并计算任意一个节点的度。下面是完整代码:
```
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
class Graph:
def __init__(self):
self.nodes = {}
def add_node(self, val):
node = Node(val)
self.nodes[val] = node
return node
def add_edge(self, val1, val2):
node1 = self.nodes[val1]
node2 = self.nodes[val2]
node1.neighbors.append(node2)
node2.neighbors.append(node1)
def degree(self, val):
node = self.nodes[val]
return len(node.neighbors)
# 创建图
graph = Graph()
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_node(4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
# 计算节点的度
print(graph.degree(1)) # 输出 2
```
在上面的代码中,我们创建了一个包含4个节点和3条边的图。然后,我们计算节点1的度,输出结果为2。