Матрица заболеваемости вместо матрицы смежности

Question

Какие задачи на графах быстрее (с точки зрения big-O) решить, используя структуры данных матрицы инцидентности вместо более распространенных матриц соседства?

Answer 1

Пространственные сложности структур:

Смежность: O (V ^ 2) Заболеваемость: O (VE)

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

Вы можете посмотреть на временную сложность некоторых типичных операций графа:

Найти все вершины, смежные с вершиной: Adj: O (V) Inc: O (VE)

Проверьте, смежны ли две вершины: Adj: O (1) Inc: O (E)

Подсчитайте валентность вершины: Adj: O (V) Inc: O (E)

И так далее.Для любого данного алгоритма вы можете использовать строительные блоки, подобные приведенным выше, чтобы вычислить, какое представление дает вам лучшую общую временную сложность.

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

Answer 2

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

Другая проблема, связанная с этим представлением, заключается в том, что хранить его нет смысла, поскольку его действительно легко вычислить динамически (чтобы ответить, что содержит данная ячейка) из списка ребер.

Это может показаться более полезным в гиперграфах, но только если оно плотное.

Так что мое мнение - это полезно только для теоретических работ.