Егор Малышев
Темы: 42
Сообщений: 132
Мой профиль
|
Хранить рёра нужно списком рёбер, в данном случае не подразумевается квадратная матрица списка рёбер, а подразумевается список рёбер, линейный по памяти.
Создаётся он так, вначале заведём два массива LAST, NEXT, дальше могут понадобиться ещё массивы, всё зависит от ситуации, но главные массивы это LAST - размерность которого O(V), и NEXT - размерность его O(E), где V - кол-во вершин, E - кол-во рёбер в графе.
Тогда в LAST[x], хранится информация о том в каком месте списка у нас лежит последнее ребро которое начинается с x, в NEXT[t] - хранится следующее ребро после ребра с номером t, при этом это ребро будет начинается с той же вершины, то есть мы по сути храним список рёбер для каждой вершины из неё выходящих, только представляя это в линейный список.
Предположим у нас есть рёбра вида, X, Y, Z. Означает добавить ребро из X -> Y, стоимостью Z. Ребро однонаправленное, понятно что если оно в обе стороны, то можно просто два раза добавить ребро, с одного и с другого конца.
Теперь рассмотрим операцию добавления одного ребра.
ADD_EDGE():
E = E + 1
NEXT[E] = LAST[X]
LAST[X] = E
FINISH[E] = Y
COST[E] = Z
Что мы сделали, запомнили для ребра E, какое будет после него, а потом затёрли информацию в массиве LAST на E, т.к как теперь последнее ребро которое мы добавили выходящее из X это E.
Вспомогательные массивы FINISH - массив конечных вершин, что бы мы могли знать куда же всё таки ведёт это ребро, COST - массив цен, что бы знать сколько стоит стоимость ребра. Их размеры O(E).
Так же понятное дело если у нас двунаправленные рёбра, и мы добавляем ребро и туда и обратно, то размер массивов будет не O(E), а O(E * 2).
Теперь рассмотрим как пробежаться по всем рёбрам вершины X.
MOVE_VER():
I = LAST[X]
WHILE (I != NULL):
// X -> FINISH[I]
I = NEXT[I]
Отсюда получаем хороший способ хранения графов, помещения их в памяти линейным видом.
|