Чтобы ответить на ваш вопрос: «В чем главное отличие представления списка и представления матрицы в матрице?»
A представление списка графика обычно представляет собой список кортежейгде каждый элемент списка является узлом, а кортежи - это узлы, связанные с ним.Скажем, у нас есть 3 узла A, B, C, поэтому у нас будет список длиной 3. Скажем, есть узел из A -> B, затем элемент в A thposition, скажем, первый элемент, будет содержать узел B.Скажем, есть также ссылка из A -> C, первый элемент будет содержать B и C.Общее пространство, необходимое для списка смежности, равно (пространство для представления узла) * (количество ребер).
С другой стороны, представление матрицы представляет собой матрицу, обычно реализуемую в виде2-й массив, где каждый узел указан на оси строк и столбцов.Если между двумя узлами есть связь, отметьте это место в матрице.Например, если у нас есть 3 узла A, B, C, у нас есть массив 3x3 array.Давайте назовем A = index 0, B = index 1, C = index 2 и предположим, что у нас есть ссылка с A -> B, затем заполните 1 на array[0][1].Если бы наш график был ненаправленным, мы также добавили бы 1 к месту в array[1][0].Общее требуемое пространство - это количество узлов, N ^ 2, умноженное на пространство, требуемое для каждой ссылки (может быть сделано с 1 битом, 0 или 1), поэтому общее количество = N ^ 2.
Списокподходит для разреженных графиков, поскольку не требует дополнительного места для хранения.То есть ссылки, которые не существуют, ничем не представлены.Напротив, если наш график очень плотный, то представление matrix лучше, потому что каждая возможная ссылка обозначается только 1 битом (0 или 1).Как видно из приведенных выше примеров, общее пространство, необходимое для представления списка, является функцией от числа ребер , в то время как пространство для матричного представления является функцией от числа узлов..
Теперь подумайте о своей конкретной проблеме.Сколько всего у вас будет узлов?Всего ребер?Это кажется разреженным или плотным?