Можно ли построить матрицу смежности для графа без хранения индексов узлов?

Question

Мне удалось реализовать решение с сохранением индекса каждого узла, но возможно ли это без индексов?Моё задание - реализовать игру Bloxrolz, вроде того.В примере, который я собираюсь показать вам, у меня нет идей, как написать код для проверки, если два узла соседствуют друг с другом.

Это просто случайное поле для игры.При чтении из файла я сохраняю здесь каждый символ в связанном списке с координатами ax, y и ID (если символ не '-').Только те, которые не являются "-", должны храниться в матрице смежности, поскольку они представляют игровую площадку, а "-" - это узлы, которые можно изменить на "-".

Я успешно реализовал решение вКстати, я не уверен, законно ли это или нет.Можете ли вы помочь мне понять, как это сделать без индексов.

Answer 1

Матрица смежности по определению является квадратной матрицей, где каждый узел представлен строкой и столбцом.Если запись в строке i и столбце j равна 1 (или выбранное вами значение), то эти два узла соединяются на графике.Следовательно, вам нужен способ сопоставления строк и столбцов с узлами и наоборот.Помещение узлов в список и использование индекса каждого узла в списке - это один из способов сделать это, но это не единственный способ.Вы можете присвоить каждому узлу идентификационный номер, и, если идентификатор каждого узла уникален и находится в пределах матрицы, вы можете использовать его.Вы можете хранить указатель на соответствующий узел в начале или конце каждой строки и столбца.Короче говоря, достаточно любого метода, который позволяет вам найти записи в матрице для данной пары узлов.

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