найти все вершины графа со степенью меньше их соседей

Question

Я пытаюсь написать алгоритм, который найдет множество всех вершин в графе со степенью, меньшей их соседей. Мой первоначальный подход заключается в том, чтобы найти степень каждой вершины, а затем проработать список, сравнивая степень каждой вершины со степенью (ами) ее соседей. К сожалению, похоже, что это может занять очень много времени. Есть ли более эффективный способ найти этот набор?

Answer 1

Возможно, "это выглядит так, как будто это может занять очень много времени", но есть лучший способ выяснить: -)

Предположим, вы сохранили свой график в виде списка смежности. Чтобы найти набор, который вы ищете, вам обязательно нужно посмотреть на все ребра, поэтому у нас есть нижняя граница , равная & # 937; (| E |) для алгоритма. Нахождение степени каждой вершины занимает время O (| E |) (потому что вы смотрите на каждое ребро ровно один раз; еще одно доказательство - использование факта, что & # 8721; d (v) = 2 | E |). Сравнение степени каждой вершины со всеми ее соседями также занимает всего O (| E |) времени (опять же, для каждого ребра выполняется только одно сравнение). Это означает, что ваш алгоритм выполняется за O (| E |) времени (около 2 | E | «шагов», но точное количество инструкций процессора зависит от вашей реализации), что соответствует нижней границе. Таким образом, ваша "грубая сила" Алгоритм, в худшем случае, по существу (с небольшой константой) настолько быстр, насколько это возможно , поэтому его не стоит оптимизировать дальше.

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

Answer 2

Один комментарий - , если вы работаете с неориентированными графиками (спасибо, Брайан Р. Бонди ), как только вы определили, что у вершины степень меньше, чем у всех ее соседей, вам не нужно проверять соседей, поскольку ни у одного из них это свойство не будет. Подумайте об использовании этих знаний, чтобы помочь вам и ускорить процесс.

Answer 3

Я бы представил жадный подход для неориентированного графа следующим образом:

let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
    let minDeg be the minimum degree of all v's neighbors
    if degree(v) < minDeg
        add v to Q*
        remove all neighbors of v from Q
        remove v from Q
        set v = new arbitrary node, v in Q
    else
        remove v from Q
        set v = v's neighbor in Q of minimum degree

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

В худшем случае это будет эквивалентно вашему алгоритму перебора. В среднем, однако, я думаю, что это должно работать лучше.