根据输入,输出有向图的拓扑排序序列。并画出有向图。输入: ABCDEF# 0,1 1,2 2,3 4,1 4,5 -1,-1
时间: 2023-09-25 19:10:12 浏览: 114
根据输入,我们可以得到以下图示:
```
A -> B -> C -> D
^ |
| |
+-------<------+
|
V
F <- E
```
其中,0-5分别代表A-F这六个顶点。根据拓扑排序的定义,我们可以得到以下序列:
```
A -> E -> F -> B -> C -> D
```
因此,输出为:`AEFBCD`
以下是Python代码实现:
```python
from collections import defaultdict
def topological_sort(graph):
# 统计每个顶点的入度数
in_degree = defaultdict(int)
for u in graph:
for v in graph[u]:
in_degree[v] += 1
# 将入度为0的顶点加入队列
queue = [u for u in graph if in_degree[u] == 0]
# 拓扑排序
result = []
while queue:
u = queue.pop(0)
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return result
# 输入
nodes, edges = input().split('#')
nodes = list(nodes)
graph = defaultdict(list)
for edge in edges.split():
u, v = map(int, edge.split(','))
if u == -1 and v == -1:
break
graph[nodes[u]].append(nodes[v])
# 拓扑排序
result = topological_sort(graph)
# 输出结果
print('->'.join(result))
```
输入:`ABCDEF# 0,1 1,2 2,3 4,1 4,5 -1,-1`
输出:`A->E->F->B->C->D`
阅读全文