преобразовать заданные ребра в матрицу смежности

Question

Если мы имеем в качестве входных данных ребра графика, например, как показано ниже в виде матрицы

    (1,2)
    (2,3)
    (3,1)

и из этих входов вы хотите создать свою матрицу смежности.

Моя идея состояла в том, чтобы перебрать матрицу и push_back в векторе, который содержит уникальные узлы (1,2,3), а затем создать нулевую матрицу с размерами, равными node_vector, снова выполнить итерацию по матрице и посмотреть, какие узлы связаны, чтобы положить 1 в нашей матрице.

Есть ли более быстрое решение, чем это?

Answer 1

Да.Если элементы пронумерованы от 1 до N, то при первом проходе все, что вам нужно сделать, это найти наибольшее число в списке ребер, и ширина вашей матрицы смежности будет равна минус один.Поиск всех уникальных узлов происходит медленнее, чем вы думаете.

Конечно, если вам действительно нужно знать, какие узлы действительно существуют, то метод, который вы перечислите, является оптимальным.