Эффективный способ практиковать алгоритмы теории графов

Я только что прочитал об алгоритме поиска в ширину в книге Introduction to Algorithms и я вручную смоделировал алгоритм на бумаге. Что я хотел бы сделать сейчас, так это реализовать это в коде для дополнительной практики.

Я думал о реализации всех структур данных с нуля (список смежности, "цвет" , «расстояние» и «родительские» массивы), но потом я вспомнил, что в настоящее время существуют библиотеки графов, такие как библиотека графов Boost и некоторые другие API графов в Питоне. Я также пытался найти некоторые проблемы, связанные с BFS, на UVA и Sphere Judge Online, но я не могу сказать, какие проблемы потребуют решения BFS.

Мой вопрос заключается в том, что было бы самым безболезненным способом практиковать эти графовые алгоритмы (не ограничиваясь только BFS, но также пригодиться, когда я хочу реализовать DFS, Dijkstra , Floyd-Warshall и т. д.). Сайты с проблемами практики приветствуются.


graph algorithm graph-theory
person Steve    schedule 04.07.2009    source источник

Ответы (5)


arrow_upward
9
arrow_downward

Я лично думаю, что лучший способ понять это - реализовать представление графа самостоятельно с нуля.

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

Но, может быть, это только я. Вышеупомянутое очень личный вкус.

person balpha    schedule 04.07.2009

arrow_upward
1
arrow_downward

Ваш вопрос показался мне интересным, я немного погуглил и нашел JGraphEd .

Он не охватывает все графовые алгоритмы, но выглядит как хороший инструмент для экспериментов.

person Nick Dandoulakis    schedule 04.07.2009

arrow_upward
1
arrow_downward

Согласен с balfa. Лучший способ действительно изучить и понять алгоритмы — это реализовать их. Просто выберите алгоритм и реализуйте его. Когда вы дойдете до точки, где вы застряли или не уверены, посмотрите на ряд существующих примеров. Тогда вы сможете сравнивать свое собственное мышление с мышлением других с позиции понимания, а не просто принимать то, что предлагается.

Как только вы узнали то, что хотите, лучший способ укрепить свое понимание — попытаться научить этому или описать это кому-то другому. У вас могут быть люди, готовые выслушать вас, или, по крайней мере, вы могли бы написать запись в блоге для людей, плохо знакомых с алгоритмом, который вы только что изучили.

Но если вы ищете "безболезненность", то, возможно, вам вообще стоит держаться подальше от алгоритмов ;-)

person user108687    schedule 04.07.2009
comment
просто для протокола, цитата должна быть самой безболезненной - person Steve; 05.07.2009

arrow_upward
0
arrow_downward

Этот сайт может вам помочь

Здесь у вас есть описание каждой проблемы с набором проблем acm. Вы можете увидеть категорию каждой проблемы и подсказку для ее решения. Просто найдите проблемы, связанные с графиком. Хороший совет — использовать эти подсказки только в том случае, если вы пытались решить проблему самостоятельно и потерпели неудачу.

person dpetek    schedule 04.07.2009

arrow_upward
0
arrow_downward

Визуализация некоторых алгоритмов кратчайшего пути на реальных данных, где исследуемая область отображается желтым цветом:

person Karussell    schedule 04.08.2012