python - Python Graph BFS 编码问题：生成课程序列

Question

我遇到了编码问题。我尝试了一个解决方案（见下文），但我被困在一个部分并想要建议。

问题：考虑一个由 N 门课程组成的学术课程。有些课程有其他课程作为先决条件。例如，如果课程 2 是课程 3 的先决条件，您必须在注册课程 3 之前完成课程 2。您一次只能参加一门课程。制定时间表以按线性顺序完成所有课程并满足每门课程的所有先决条件。如果存在多个可能的时间表变体，请使用索引较小的课程首先完成的时间表。

例如：

4
1 0
2 0
3 1 2

第一行表示学术课程中有 4 门课程。第二行和第三行定义课程 0 必须在课程 1 和 2 之前修读。第四行定义课程 1 和 2 必须在课程 3 之前修读。

输出：一个包含以空格分隔的课程列表的时间表，按照他们的出席顺序排列。例如：

0 1 2 3 

对于此示例，存在另一个时间表 0 2 1 3。但我们必须选择变体 0 1 2 3，其中课程 1（具有较小的索引）在课程 2（具有较大的索引）之前参加。

Test 1
Test Input
4
1 0
2 0
3 1 2
Expected Output
0 1 2 3

Test 2
Test Input
7
0 1 2
1 3
2 3
3 4 5
4 6
5 6
Expected Output
6 4 5 3 1 2 0

Test 3
Test Input
8
4 0 2
0 1 6
2 3 7
1 5
6 5
3 5
7 5
Expected Output
5 1 3 6 0 7 2 4

解决方案尝试：

我认为这只是在无向图上执行 BFS，课程和先决条件作为相互连接的边。

import collections 

graph = collections.defaultdict(set)

def add_edge_undirected(graph, u, v):
    if not (u in graph and v in graph[u]) or not (v in graph and u in graph[v]):
        graph[u].add(v)
        graph[v].add(u)

def bfs(graph, root, ans): 
    visited, queue = set(), collections.deque([root])
    visited.add(root)
    while queue: 
        print(queue)
        vertex = queue.popleft()
        ans.append(vertex)
        for neighbour in graph[vertex]: 
            if neighbour not in visited: 
                visited.add(neighbour) 
                queue.append(neighbour)


def main():
    inputs = [[4, 0, 2], [0, 1, 6], [2, 3, 7], [1, 5], [6, 5], [3, 5], [7, 5]] # test case 3
    start = 5 # we are starting from vertex 5 because that is the first course in the entire sequence

    for prereq in inputs:
        for i in range(1, len(prereq)):
            add_edge_undirected(graph, prereq[0], prereq[i])

    ans = []
    bfs(graph, start, ans)
    print(ans)

main()

样本输入：测试用例 3。终端输出：[5, 1, 3, 6, 7, 0, 2, 4] 预期输出：[5, 1, 3, 6, 0, 7, 2, 4]

这是我遇到的问题。(1) bfs 没有考虑应该学习的课程的顺序（优先级）。关于如何考虑优先级的任何建议？(2) 如何计算 bfs 的起始顶点？我可以通过绘制图表来判断，但我如何从输入中判断？

任何建议，将不胜感激

标签： pythongraphdepth-first-searchbreadth-first-searchtopological-sort