拓扑排序实现课程表 任务:编写函数实现图的拓扑排序,用以实现课程的安排。 具体要求:(1)课程的输入;(2)课程的安排;(3)课程的安排查询;等待
时间: 2024-03-27 12:36:19 浏览: 46
好的,我可以为您提供拓扑排序实现课程表的代码示例,具体如下:
```python
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.vertices = vertices
def addEdge(self, u, v):
self.graph[u].append(v)
def topologicalSort(self):
in_degree = [0] * self.vertices
for i in self.graph:
for j in self.graph[i]:
in_degree[j] += 1
queue = []
for i in range(self.vertices):
if in_degree[i] == 0:
queue.append(i)
count = 0
top_order = []
while queue:
u = queue.pop(0)
top_order.append(u)
for i in self.graph[u]:
in_degree[i] -= 1
if in_degree[i] == 0:
queue.append(i)
count += 1
if count != self.vertices:
print("There is a cycle in the graph")
else:
print("Topological order of the graph:", top_order)
g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
g.topologicalSort()
```
这个示例代码中,我们定义了一个名为 `Graph` 的类来表示图,并实现了 `addEdge` 和 `topologicalSort` 方法。在这个示例中,我们创建了一个包含 6 个顶点的有向图,并在其中添加了多个边。最后,我们调用 `topologicalSort` 方法来进行拓扑排序,并输出结果。
您可以根据您的需求进行修改,例如改变图的大小、添加或删除边,以及查询课程的安排等。希望这个示例能对您有所帮助!
阅读全文
相关推荐



















