Представление матрицы смежности/списка

Question

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

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

Какова будет лучшая структура данных для представления коллекции узлов и соседних узлов каждого из них?

Answer 1

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

 0 --- 1------5---6 
     | \ \  |/
     | \ \ |/
     2 3----4---7 

      0 1 2 3 4 5 6 7 
      ----------------- 
     0 | 0 1 1 1 0 0 0 0 
     1 | 1 0 0 0 1 1 0 0 
     2 | 1 0 0 0 0 0 0 0 
     3 | 1 0 0 0 1 0 0 0 
     4 | 0 1 0 1 0 0 0 1 
     5 | 0 1 0 0 0 0 1 1 
     6 | 0 0 0 0 0 1 0 1 
     7 | 0 0 0 0 1 1 1 0 
      ------------------ 

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