bender2002Пишу программу по работе с графом в С++
По-моему мнению, сама структура для описания вершины графа должна содержать динамический массив указателей на те вершины, с которым он связан
Подскажите, правильно ли я думаю, и как это реализовать на С++
Заранее спасибо!!!!
ИМХО, с одной стороны правильно (если рассматривать с точки зрения вершин графа).
Но, если рассматривать с другой стороны (с точки зрения минимизации памяти, удобства работы и т.д.) то, опять же ИМХО, может быть, лучше использовать матрицу смежности, где указывается (на пересечении соответствующих строки и столбца) вес/цена дуги или 0, если вершины не связаны. Это получается двумерный массив размером NxN, симметричный относительно главной диагонали при неориентированном графе и, в общем случае, не симметричный при ориентированном.
Кроме того, здесь (в матрице смежности) легко можно учесть факт, что в ориентированном графе прямая и обратная дуги, соединяющие две вершины, могут иметь разный вес/цену