График Запрос по краю

Question

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

Другое представление графика - это incidence matrix, где края инцидентности записываются в матрицу. Я понимаю, что они представляют собой ту же информацию, что и предыдущие методы на основе узлов.

Вопрос в том, есть ли какие-либо графические запросы/рабочие нагрузки/алгоритмы, которые могут извлечь выгоду из структуры матрицы инцидентов, а не использовать узловые структуры, то есть благоприятствовать структуре на основе краев? Когда точно используется матрица инцидентов?

Answer 1

я могу думать только об одном случае, когда матрица инцидентности может оказаться быстрее:

Нахождение степени узла или нахождение соседних узлов является операцией со сложностью O (V) при использовании матрицы смежности и О (Е) при использовании матрицы инцидентов.

Обычно E> V, но это может быть не так, если граф имеет много узлов с 0 степенями. Поскольку поиск смежных узлов является основной операцией, многие алгоритмы могут оказаться более быстрыми на таких графах.