Python График BFS Кодирование Вопрос: Генерация последовательности курса - PullRequest
Новая
       65

Python График BFS Кодирование Вопрос: Генерация последовательности курса

0 голосов
/ 27 февраля 2020

У меня проблемы с вопросом кодирования. Я попытался найти решение (см. Ниже), но застрял в одной части и хотел бы получить предложения.

Вопрос: Рассмотрим программу Academi c, которая состоит из N курсов. Некоторые курсы имеют другие в качестве предварительных условий. Например, если курс 2 является обязательным условием курса 3, вы должны пройти курс sh курс 2, прежде чем записаться на курс 3. Вы можете посещать только один курс за раз. Составьте расписание, чтобы завершить все курсы в линейной последовательности и удовлетворить все предпосылки для каждого курса. Если существует более одного варианта возможного расписания, используйте расписание, в котором курсы с меньшими индексами заканчиваются первыми.

Например: 

4
1 0
2 0
3 1 2

Первая строка означает, что в программе имеется 4 курса. программа Academi c. Вторая и третья строки определяют, что курс 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? Я могу сказать по графику, но как я могу узнать из ввода?

Любые предложения будут оценены

...