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

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

2 голосов
/ 13 ноября 2008

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

Ответы [ 3 ]

3 голосов
/ 13 ноября 2008

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

2 голосов
/ 14 ноября 2008

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

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

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

1 голос
/ 13 ноября 2008

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

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

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

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

...