Найти гамильтоновский путь на турнире с списками смежности в Python

Question

Турнир - это полный, направленный граф, который задает любые две вершины u и v, между ними существует направленное ребро (если u выиграно над v, тогда ребро от u до v).

Гамильтоновский путь всегда существует в турнире. Поэтому заданные списки смежности в форме {u: [v, w], v: [w]}, где есть направленное ребро от u до w, u до v и v to w, как найти то, что гамильтонов путь есть и печатать верификации в порядке?

Даже если вы не знаете python или что-то еще, просто алгоритм будет очень полезен. Я подумал об этом, и, полагаю, мне нужно начать с вершины высшей степени? Затем добавьте вершину со второй наивысшей степенью и т. Д. До вершины с наименьшей степенью. Но я не вижу, как это безопасный метод, вершина с наивысшей степенью могла быть избита вершиной со второй самой высокой.

Благодарим за любую помощь заранее!

Answer 1

Вы можете решить эту проблему рекурсивно. Предположим, что у вас есть n+1 вершины с именем v_0 до v_n. v_1 - v_n и грани между ними для турнира размером n, поэтому мы можем предположить, что у нас есть гамильтонов путь, содержащий v_1 до v_n. Переименуйте их в соответствии с этим путем как u_1 до u_n. Теперь найти u_i такие, что u_i выиграл более v_0 и v_0 выиграл более u_i+1 (Здесь следует позаботиться о маргинальных узлов: v_0 выиграл более u_1 или u_n выиграл более v_0). После нахождения такого i, общий путь гамильтонов может быть выполнен в виде:

u_1 , ... , u_i , v_0 , u_i+1 , ... , u_n 

Этот алгоритм имеет время выполнения O (N^2). Для этой задачи существует O (nlogn) алгоритм.