Турнир - это ориентированный граф (орграф), полученный путем назначения направления для каждого ребра в неориентированном полном графе. То есть, это ориентированный граф, в котором каждая пара вершин соединена одним направленным ребром.График турнира
Структура данных - матрица смежности.
Какой алгоритм можно найти, если граф является графиком турнира?
Есть п^2 записи в матрицу смежности, и вам нужна информация, которая во всех записях, чтобы решить эту проблему. (Вам нужно 1, чтобы проверить, что существуют соответствующие ребра, а 0 - проверить, что обратные края не существуют.) Таким образом, поскольку вам нужно прочитать по крайней мере N^2 записи из матрицы, общая проблема должна выполняться не менее O (N^2) времени.
Что касается попыток поиска BFS: если ваш обход принимает O (n^2) - что будет, из-за необходимости поиска краев в матрице смежности - тогда не имеет значения, является ли проверка на заднем крае постоянное время, общий алгоритм по-прежнему равен O (n^2).
Еще один способ взглянуть на эту проблему: поскольку число ребер равно числу возможных пар вершин, будет n * (n-1)/2 ребра, то есть O (n^2). Ваш обход - это O (V + E), что, таким образом, O (n + n^2), и, следовательно, O (n^2).
Поскольку наилучшим вариантом для этого алгоритма является O (n^2), вы можете просто просто пропустить верхнюю правую половину матрицы (над диагональю) и проверить, что для каждой из этих записей либо а) это 1, или б) его транспозиция эквивалент 1.
Редактировать: пропущена часть, где график был заполнен.
Если M ваша матрица смежности, Mt транспонированная матрица, ~M матрица со всеми «бит» перевернутых и A^B является XOR побитно между двумя матрицей.
Тогда матрица представляет собой турнир тогда и только тогда:
~(M^Mt) = I
Это не гарантирует, что все пары вершин соединены. – Amber
Foreach? Вы не можете сделать foreach, это будет O (n^2). В чем смысл каждого края? Я проверяю его для каждого края, которое я посетил. – DarthVader
Дав также прав. – DarthVader
чтобы добавить комментарий Tonfa в:
Краткое: алгоритм «для каждого я ≠ J, проверьте, чтобы увидеть, что именно один из (i, j) и (j, i) в вашем графике «асимптотически оптимальны.
Подробнее: Чтобы просто читать в матрице смежности будет считать вас Q (п) время. Таким образом, нет возможности решить эту проблему в o (n) времени. Но давайте проигнорируем ввод.
Предположим, что матрица уже находится в памяти. Чтобы гарантировать, что неориентированная версия вашего графика будет завершена, вам нужно как-то определить, что для каждого i ≠ j по крайней мере один из ребер (i, j) и (j, i) находится в вашем графике. Поскольку у вас есть только граф смежности, это означает, что вам придется в какой-то момент посетить хотя бы один из (i, j) или (j, i) для каждого i ≠ j. Другого способа гарантировать полноту нет. Для проверки этого потребуются шаги n (n + 1)/2 = O (n).
«Подробнее: просто прочитать в матрице смежности возьмем ваше время O (n2). Таким образом, в o (n2) времени нет возможности решить эту проблему». Не правда. У вас может быть несколько компонентов, которые принимают O (n^2) раз, а результат по-прежнему равен O (n^2). Помните, что нотация O() - это * порядок *, а не фактическая функция времени. – Amber
Это звучит как домашняя проблема. Возможно, вы могли бы разобраться в своих мыслях относительно проблемы, и мы могли бы помочь вам, где бы вы ни застряли? – Amber
, где мой комментарий пошел? DAV? – DarthVader
Я понятия не имею; Я видел это раньше, а затем он исчез и для меня. – Amber