编程实现有向图图的邻接表存储,并计算给定结点的入度和初度。
时间: 2024-03-20 18:40:42 浏览: 97
-针对一按照邻接表存放的有向图,计算图中节点的出度和入度
5星 · 资源好评率100%
好的,以下是 Python 代码实现:
```python
class Graph:
def __init__(self, nodes):
self.nodes = nodes
self.adj_list = {node: [] for node in nodes}
def add_edge(self, u, v):
self.adj_list[u].append(v)
def indegree(self, node):
indeg = 0
for u in self.adj_list:
if node in self.adj_list[u]:
indeg += 1
return indeg
def outdegree(self, node):
return len(self.adj_list[node])
```
其中,`Graph` 类中的 `__init__` 方法用于初始化有向图,`add_edge` 方法用于添加边,`indegree` 和 `outdegree` 方法分别用于计算给定结点的入度和出度。
例如,我们可以这样使用代码:
```python
nodes = ['A', 'B', 'C', 'D', 'E']
edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A'), ('D', 'E')]
g = Graph(nodes)
for u, v in edges:
g.add_edge(u, v)
print(g.indegree('A')) # 输出 1
print(g.outdegree('D')) # 输出 2
```
这里我们定义了一个包含 5 个结点和 5 条边的有向图,并计算了结点 'A' 的入度和结点 'D' 的出度。
阅读全文