|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
01.06.2011, 08:02 | #1 |
Форумчанин
Регистрация: 08.11.2010
Сообщений: 593
|
Теория Графов
Добрый день, никто не может подкинуть хорошей теории по графам?
Вплоть от того, какую структуру данных лучше выбрать для хранения графа, и заканчивая различными алгоритмами(поиск циклов например, эйлеровых путей) |
01.06.2011, 09:07 | #2 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Обычно графы хранят в деревьях, но можно и в матрицах смежности.
Я пердпочитаю матрицы смежности. Во-первых, это проще чем организовывать структуру деревьев. Во-вторых, решение большинства задач производится через них. Например потоки в сетях, задача коммивояжера, задача о назначениях...
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
01.06.2011, 10:28 | #3 |
С++
Форумчанин
Регистрация: 22.09.2008
Сообщений: 791
|
С другой стороны, матрицы смежности занимают гораздо больший объем памяти, нежели дерево, и иногда могут неэффективными (в случае, если между многими вершинами нет ребер). Еще они не могут обработать ситуацию, когда существует несколько ребер между одной парой вершин с различными весами (но это можно обойти в условиях задачи).
Но Smitt&Wesson прав, реализовывать алгоритмы на матрицах значительно проще, и в этом они очень выигрывают.
Форматируйте код, будьте людьми.
|
01.06.2011, 10:54 | #4 | ||
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Цитата:
Цитата:
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
||
03.06.2011, 09:00 | #5 |
Форумчанин
Регистрация: 08.11.2010
Сообщений: 593
|
В общем, спасибо за советы. решил использовать для невзвешанного графа матрица смежности, для взвешанного матрицу транзитивного замыкания)
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Теория Графов | Verc | Фриланс | 0 | 27.03.2011 21:39 |
Теория графов в программировании | Ltyxbr | Помощь студентам | 3 | 19.06.2010 18:16 |
TurboPascal: теория графов | ulala | Помощь студентам | 0 | 17.12.2009 16:23 |
С++. Теория графов | curly182 | Общие вопросы C/C++ | 3 | 28.05.2009 23:14 |