Теория Графов

[CodeNOT]

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

[Smitt&Wesson]

Обычно графы хранят в деревьях, но можно и в матрицах смежности.
Я пердпочитаю матрицы смежности. Во-первых, это проще чем организовывать структуру деревьев. Во-вторых, решение большинства задач производится через них.
Например потоки в сетях, задача коммивояжера, задача о назначениях...

[Granus]

С другой стороны, матрицы смежности занимают гораздо больший объем памяти, нежели дерево, и иногда могут неэффективными (в случае, если между многими вершинами нет ребер). Еще они не могут обработать ситуацию, когда существует несколько ребер между одной парой вершин с различными весами (но это можно обойти в условиях задачи).
Но Smitt&Wesson прав, реализовывать алгоритмы на матрицах значительно проще, и в этом они очень выигрывают.

[Smitt&Wesson]

Сообщение от Granus

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

Ну, если нам не надо создавать граф всех дорог России, эта разница не существенна.

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

А ситуацию нескольких дуг между двумя вершинами, легко обойти введением фиктивных вершин.

[CodeNOT]

В общем, спасибо за советы. решил использовать для невзвешанного графа матрица смежности, для взвешанного матрицу транзитивного замыкания)