) 键盘输入数据,建立一个有向图的邻接表。 (2) 输出该邻接表。 (3) 在有向图的邻接表的基础上计算各顶点的度,并输出
时间: 2024-03-03 11:51:14 浏览: 48
好的,让我来解答你的问题。
首先,让我们来看看如何建立有向图的邻接表。假设输入的数据格式为:
```
5 6
1 2
1 3
2 3
2 4
3 4
4 5
```
其中第一行的两个数字表示顶点数和边数,接下来的每一行表示一条边。
那么我们可以使用 Python 语言来实现建立邻接表的过程,代码如下:
```python
n, m = map(int, input().split())
# 初始化邻接表
adj = [[] for i in range(n)]
# 添加边
for i in range(m):
u, v = map(int, input().split())
adj[u-1].append(v)
# 输出邻接表
for i in range(n):
print(i+1, end=': ')
for j in adj[i]:
print(j, end=' ')
print()
```
接下来,我们来看看如何计算各顶点的度。有向图的度分为出度和入度,出度表示从该顶点出发的边的数目,入度表示指向该顶点的边的数目。
那么我们可以使用以下代码来计算各顶点的度:
```python
# 计算各顶点的出度
out_degree = [len(adj[i]) for i in range(n)]
# 计算各顶点的入度
in_degree = [0] * n
for i in range(n):
for j in adj[i]:
in_degree[j-1] += 1
# 输出各顶点的度
for i in range(n):
print("顶点 %d 的度为:出度 %d,入度 %d" % (i+1, out_degree[i], in_degree[i]))
```
这样,我们就完成了建立有向图的邻接表、输出邻接表和计算各顶点的度的过程。