Версия для печати темы

Автор: Matadora 14.11.2010, 13:58

задали написать прогу на С, которая находит диаметр графа
без понятия вообще, вокруг все такие умные и толком не могут мне сказать где искать хорошую литературу... я вообще-то лучше понимаю на практике, вот увижу какой-то пример по нужной теме и уже более-менее плаваю

так что надеюсь на вас, уважаемые форумчане
подскажите где можно онлайн почитать хорошую литературу про графы, и где есть примеры решений простых или не очень, задач на С или С#

Автор: tig81 14.11.2010, 14:02

Не поняла, вы не знаете как реализовать на С или не знаете, что такое диаметр графа?
Посмотрите http://www.google.com.ua/search?hl=ru&client=firefox&hs=OYy&rls=org.mozilla%3Aru%3Aofficial&q=%D0%BD%D0%B0%D0%B9%D1%82%D0%B8+%D0%B4%D0%B8%D0%B0%D0%BC%D0%B5%D1%82%D1%80+%D0%B3%D1%80%D0%B0%D1%84%D0%B0%2C+%D0%A1&aq=f&aqi=&aql=&oq=&gs_rfai= и http://www.google.com.ua/search?hl=ru&client=firefox&hs=HEJ&rls=org.mozilla%3Aru%3Aofficial&q=%D0%B4%D0%B8%D0%B0%D0%BC%D0%B5%D1%82%D1%80+%D0%B3%D1%80%D0%B0%D1%84%D0%B0&aq=f&aqi=&aql=&oq=&gs_rfai=, может что-то прояснится.

Автор: Harch 16.11.2010, 11:18

Как задан граф?

Автор: Botan 26.12.2010, 11:19

Например такой наивный метод: запускаем алгоритм флойда. потом в матрице, которую он построит ищем самое большое число.. это и будет диаметр графа.

З.Ы. Если вы не знаете, что такое алгоритм флойда, то есть http://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла. там хорошо объяснено.
З.З.Ы. Это наивный метод и работает за кубическое время. Существует метод, работающий за линейное время, но его трудно объяснять на пальцах.



хм.. таких пока не знаю... Зато могу посоветовать книгу, где есть много алгориитмов и структур данных... там всё хорошо описано и доказано.. приведён псевдокод...
Т.Кормен, Ч. Лейзерсон, Р.Ривест, К.Штайн Алгоритмы, построение и анализ. (в некоторых кругах известна под именем "кормен").
А если вам нужны конкретные задачи, то есть например http://www.topcoder.com/.