Алгоритмы на графах

Представление графа в ЭВМ

Достоинства и недостатки указанных способов хранения

2. Достоинством списка смежности является, то, что для хранения всего списка смежности требуется порядка 2jE(G)j

ячеек памяти (поскольку в списке смежности каждое ребро fi; jg встречается дважды, один раз в L[i], а другой в L[ j])

Алгоритмы на графах

Представление графа в ЭВМ

Достоинства и недостатки указанных способов хранения

2. Достоинством списка смежности является, то, что для хранения всего списка смежности требуется порядка 2jE(G)j

ячеек памяти (поскольку в списке смежности каждое ребро fi; jg встречается дважды, один раз в L[i], а другой в L[ j])

Недостатком списка смежности является то, что проверка лежит ли ребро fi; jg требует просмотра списка L[i] (èëè L[ j]).

Ясно, что если список большой, то этот процесс может затянуться

Алгоритмы на графах

Представление графа в ЭВМ

Достоинства и недостатки указанных способов хранения

2. Достоинством списка смежности является, то, что для хранения всего списка смежности требуется порядка 2jE(G)j

ячеек памяти (поскольку в списке смежности каждое ребро fi; jg встречается дважды, один раз в L[i], а другой в L[ j])

Недостатком списка смежности является то, что проверка лежит ли ребро fi; jg требует просмотра списка L[i] (èëè L[ j]).

Ясно, что если список большой, то этот процесс может затянуться

Таким образом, если граф плотный (т. е. имеет достаточно большое число ребер), то лучше использовать матрицу смежности.

Алгоритмы на графах

Представление графа в ЭВМ

Достоинства и недостатки указанных способов хранения

2. Достоинством списка смежности является, то, что для хранения всего списка смежности требуется порядка 2jE(G)j

ячеек памяти (поскольку в списке смежности каждое ребро fi; jg встречается дважды, один раз в L[i], а другой в L[ j])

Недостатком списка смежности является то, что проверка лежит ли ребро fi; jg требует просмотра списка L[i] (èëè L[ j]).

Ясно, что если список большой, то этот процесс может затянуться

Таким образом, если граф плотный (т. е. имеет достаточно большое число ребер), то лучше использовать матрицу смежности.

В противном случае список смежности более эффективен, особенно, если удается придумать алгоритм, который нивелирует его недостаток.

Алгоритмы на графах