使用字典和集合模拟下面有向图结构,请使用相关序列结构实现:输出有向图中某个节点的“入度”与“出度”,以及该节点与其它节点的所有进、出
时间: 2024-11-15 21:22:25 浏览: 2
-针对一按照邻接表存放的有向图,计算图中节点的出度和入度
5星 · 资源好评率100%
在Python中,我们可以使用字典(`dict`)来模拟有向图的邻接表结构,其中键是节点,值是一个列表,包含所有指向该节点的边。对于每个边,我们可以在对应的列表中存储另一个字典,用于追踪入度(进入节点的数量)和出度(从该节点出发的数量)。集合则可以用来快速判断两个节点是否相邻。
这里是一个简单的示例:
```python
class Graph:
def __init__(self):
self.graph = {} # 字典表示邻接表
def add_edge(self, node_from, node_to):
if node_from not in self.graph:
self.graph[node_from] = []
if node_to not in self.graph:
self.graph[node_to] = []
# 添加边并更新邻接表
self.graph[node_from].append(node_to)
self.graph[node_to]['out'] += 1 # 更新出度
def get_degrees(self, node):
if node in self.graph:
return {
'in': len(self.graph[node]), # 入度
'out': self.graph[node]['out'], # 出度
'neighbors': set(self.graph[node]) # 进来的邻居
}
else:
return None # 节点不存在
# 使用示例
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
degrees_A = g.get_degrees('A') # {'in': 2, 'out': 2, 'neighbors': {'B', 'C'}}
degrees_D = g.get_degrees('D')
阅读全文