Блог

Я нашел решение этого вопроса топологической сортировки, но это не решение, с которым я сталкивался ни в одном из своих исследований, что заставляет меня полагать, что оно не самое оптимальное. Вопрос (от algoexpert) звучит примерно так: «верните один из возможных обходов графа, учитывая граф, где каждый узел представляет задание, а каждое ребро представляет предварительное условие этого задания. Первый параметр — это список чисел, представляющих задания, второй параметр — это список массивов (размер 2), где первое число в массиве представляет предварительное условие для задания, являющегося вторым номером. Например, входные данные([1,2,3], [[1,3],[2,1],[2,3]]) => [2, 1, 3]. Примечание: график может быть нециклическим, и тогда алгоритм должен вернуть пустой массив. Пример, входные данные([1,2], [[1,2],[2,1]]) => [].

Популярное оптимальное решение немного сбивает меня с толку, поскольку я пытался его реализовать, но постоянно возникают ситуации, когда мой алгоритм обнаруживает цикл, а короткое замыкание возвращает пустой массив. Этот алгоритм «работает в обратном направлении» в первую очередь в глубину, при этом «незавершенные» и «посещенные» узлы сохраняются в памяти во время поиска по графу.

Мой алгоритм изначально находит узлы графа без предварительных запросов (поскольку они могут быть немедленно добавлены в возвращаемый массив) и удаляет этот узел из предварительных запросов всех других узлов. Пока происходит это удаление, если у этого узла теперь 0 предварительных запросов, добавьте его в стек. Когда размер стека достигает 0, верните возвращаемый массив, если его размер соответствует размеру первого параметра (список заданий), в противном случае верните пустой массив, что в данном случае означает, что в графике присутствовал цикл. Вот код для моего алгоритма:

 def topologicalSort(jobs, relations):
    rtn = []
    jobsHash = {}
    stackSet = set()
    for job in jobs:
        stackSet.add(job)
    for relation in relations:
        if relation[1] in stackSet:
            stackSet.remove(relation[1])
        if relation[0] not in jobsHash:
            jobsHash[relation[0]] = {"prereqs": set(), "depends": set()}
        jobsHash[relation[0]]["depends"].add(relation[1])
        if relation[1] not in jobsHash:
            jobsHash[relation[1]] = {"prereqs": set(), "depends": set()}
        jobsHash[relation[1]]["prereqs"].add(relation[0])
        if jobsHash[relation[0]]["prereqs"].__contains__(relation[1]):  # 2 node cycle shortcut
            return []
    stack = []
    for job in stackSet:
        stack.append(job)
    while len(stack):
        job = stack.pop()
        rtn.append(job)
        clearDepends(jobsHash, job, stack)
    if len(rtn) == len(jobs):
        return rtn
    else:
        return []


def clearDepends(jobsHash, job, stack):
    if job in jobsHash:
        for dependJob in jobsHash[job]["depends"]:
            jobsHash[dependJob]["prereqs"].remove(job)
            if not len(jobsHash[dependJob]["prereqs"]):
                stack.append(dependJob)
        jobsHash[job]["depends"] = set()


print(topologicalSort([1,2,3,4],[[1,2],[1,3],[3,2],[4,2],[4,3]]))
 

Я обнаружил, что этот алгоритм имеет временную сложность O (j d) и пространственную сложность O (j d), что также соответствует атрибутам популярных алгоритмов. Мой вопрос в том, нашел ли я правильные сложности и является ли это оптимальным решением этой проблемы. Спасибо!