Ненаправленный граф смежности (информатика)

Question

У меня есть неориентированный граф G = (V, E) с узлами, помеченными 1, 2, 3, ..., n, и конкретным узлом k в V.

У меня есть два представления этогографик: Матрица смежности и Список смежности

Как мне выяснить, смежен ли узел k со всеми другими узлами графа?Это часть большей проблемы, которая у меня есть.

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

Спасибо

Answer 1

с использованием вспомогательных матриц, проверьте строку k на 1 во всех компонентах, кроме k -ой.

используя списки примыканий (при условии, что у вас нет мультиграфа, а n - количество вершин графа), проверьте размер списка n-1, который должен быть O (1).

С наилучшими пожеланиями, Carsten

Answer 2

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