Рассмотрим ориентированные графы. Мы называем узел суперзвездой том и только в том случае, если от него невозможно связаться с другим узлом, но все остальные узлы имеют ребро к . Формально:v
v
с число узлов в графе. Например, на приведенном ниже графике незаполненный узел является суперзвездой (а другие узлы - нет).
[ источник ]
Как вы можете определить все суперзвезды в ориентированных графах за время? Подходящее графическое представление может быть выбрано из обычных кандидатов ; пожалуйста, воздержитесь от использования представлений, которые перемещают сложность проблемы к предварительной обработке.
Никакие предположения относительно плотности не могут быть сделаны. Мы не предполагаем, что граф содержит суперзвезду; если его нет, алгоритм должен его распознать.
Обозначение : - это число исходящих ребер в узле, аналогично для входящих ребер.я н д е г
источник
Ответы:
Мы можем исключить все, кроме одной из вершин, проверив наличие ребер, потому что мы можем исключить одну возможность для каждого проверяемого ребра. В частности, если существует ребро, идущее от к , мы исключаем и переходим к (так как из него можно добраться до другой вершины); если нет, мы исключаем (так как он не может быть достигнут из ). Как только мы достигаем последней вершины, любую вершину, не удаляемую, следует сравнивать с каждой другой вершиной (убедитесь, что условие суперзвезды поддерживается: есть ребро входящее, но не исходящее), пока оно не будет удалено или подтверждено как суперзвезда. Какой-то псевдокод:x y x y y xn - 1 Икс Y Икс Y Y Икс
Давайте рассмотрим пример, чтобы проиллюстрировать метод. Возьмите этот массив с исходной вершиной сверху и местом назначения сбоку. 1 обозначает ребро:
Я выделю вершины, которые мы исключили, как потенциальных суперзвезд. Я буду использовать зеленый и красный, чтобы указать края, на которые мы смотрим, когда они есть, и не содержат искомого края, и синий, чтобы указать, где мы уже смотрели.
Начнем с рассмотрения вершин 1 и 2.
Мы видим, что такого ребра нет, поэтому исключаем 1 и берем 3 в качестве текущей вершины. Напомним, что мы уже удалили 2, поэтому посмотрим, есть ли преимущество от 4 до 3:
Имеется ребро от 4 до 3, поэтому мы исключаем 4. На этом этапе мы удалили все, кроме одной из вершин (3), поэтому проверьте его ребра и посмотрите, подходит ли оно:
Существует преимущество от 1 до 3, но не наоборот, поэтому 3 все еще является кандидатом.
Существует также преимущество от 2 до 3, но не наоборот, так что 3 все еще является кандидатом.
Есть преимущество от 4 до 3, но не от 3 до 4; это завершает нашу проверку 3-х ребер, и мы обнаружили, что это на самом деле суперзвезда.
Поскольку мы исключаем одну вершину в качестве возможной суперзвезды в каждой из первых проверок ребер, наилучшим случаем является то, что я проверка исключает конечную вершину для сложности . В худшем случае (последняя или вторая-последняя вершина является суперзвездой, или последняя проверка дисквалифицирует ее), после первых сравнений мы сравниваем кандидата с больше вершин, для в худшем случае сложность ( ). Итак, этот алгоритм .n n n - 1 2 × ( n - 1 ) 3 n - 3 O ( n ) Θ ( n )n - 1 N N n - 1 2 × ( n - 1 ) 3 n - 3 O ( n ) Θ ( н )
источник
Разве это не проблема знаменитости ?
Будет только одна суперзвезда (знаменитость), если она есть.
Мы используем представление матрицы смежности, где если существует направленное ребро от до , в противном случае оно равно . (Я предполагаю, что это разрешено).i j 0A [ i , j ] = 1 я J 0
Посмотрев на (может быть сделано за время), мы можем исключить хотя бы одного из них в качестве кандидата на звание знаменитости: если , тогда вы можете устранить . Если мы можем исключить .A [ i , j ] O (1) A [ i , j ] = 1 я A [ i , j ] = 0 J
Вести список текущих кандидатов, исключая одного за другим. Связанного списка должно быть достаточно.
В конце вы можете проверить, действительно ли ваш кандидат суперзвезда.
Этот алгоритм будет .O ( n )
источник
Этот ответ касается версии вопроса, где было возможно любое представление графа, а не текущей версии вопроса.
Сохраните ваш график в виде пары списков смежности и списка обратных смежностей, где каждый список содержит, кроме того, длину списка, а следовательно, число внешних и внутренних ребер соответственно.
Предварительная обработка: вычисляет список обратной смежности (то есть список ребер). Стоимость .O ( | E| )
Пройдите по спискам и выберите любой узел, у которого число внешних ребер равно а количество внутренних ребер равно . Стоимость .0 n - 1 O ( | N| )
источник
Просто для справки, это псевдокод рекурсивной версии того, что написал Кевин.
источник