Представление отсутствия ребра в матрице смежности взвешенного графа

Question

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

Учитывая, что 0 и отрицательные числа будут правильным весом для ребра, как я могу представить отсутствие ребра между двумя узлами?

Answer 1

Вы можете использовать вместо числа (double) такую ​​структуру:

struct weight
{
   double weight;
   bool edge_exists;
};

и создайте матрицу смежности weight. Таким образом, если edge_exist s имеет значение false, нет смысла проверять weight, иначе weight будет иметь смысл.

Я бы использовал вышеприведенное, если бы каждое (?) double могло быть возможным значением веса.

Answer 2

Если вы используете C99 или более позднюю версию, вы можете использовать макрос INFINITY, определенный в math.h, и назначить всем несуществующим ребрам вес INFINITY.

Подробнее об использовании бесконечности см. Здесьв C: Как использовать nan и inf в C?

(Вы также можете технически использовать NaN, но это не гарантируется, и я думаю, что использование бесконечности работает лучше во многихалгоритмы в любом случае)

Answer 3

Как насчет бессмысленного (я полагаю, вы предполагаете, что все веса должны быть положительными) числа, такого как -1?

Это будет держать код светом (не нужно добавлять дополнительные данныеструктуры), и было бы просто запомнить.