Алгоритмы обучения графику

Question

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

Это язык агностик, но я больше всего знаком с python и не имею большого опыта работы с FP.

Answer 1

Оба очень хороши:

• The Algorithm Design Manual

• Algorithms in C++ Part 5: Graph Algorithms (Не беспокойтесь о бит C++, также имеет псевдокод)

Бесплатное:

• Chapter 5. Graphs and graph algorithms

Answer 2

Steve Yegge говорит, что this - потрясающая книга по алгоритмам, в которых широко используются графики.

Answer 3

я узнал много о графиках из книги связаны ниже ... это одна из моих любимых книг: http://books.google.com/books?id=5l5ps2JkyT0C&printsec=frontcover&dq=a+course+in+combinatorics&source=bl&ots=wSYYY6KPuI&sig=mZLrdj0xo2mTxW4MxYt4tW_E-10&hl=en&ei=PoHHTOaROIHGlQegn8ibAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCkQ6AEwAQ#v=onepage&q&f=false

A Course in Combinatorics 
J. H. van Lint, R. M. Wilson 
Cambridge University Press 
ISBN 0 521 00601 5

Answer 4

Я хотел бы предложить, что, когда вы будете изучать любые алгоритмы, то не думать о кодировании. Алгоритмы полностью математичны, и вы должны относиться к ним одинаково. Когда вы изучаете что-то вроде алгоритма Graph Spanner, не думайте, как его кодировать, как представлять их. Сначала оцените, почему алгоритм важен и нетривиальен. Затем попробуйте некоторые тривиальные решения и сравните их сложность. Далее посмотрите, как выглядят оптимальные решения и пытаются получить их свойства. Используйте бумагу и ручку, а не IDE, попробуйте вывести и доказать леммы и так далее. Затем, наконец, посмотрите, как вы можете написать псевдокод для решения проблемы. Если вы сделаете это, тогда вы разработаете интимное отношение к алгоритмам, и тогда вы обнаружите, что их гораздо легче решить, так как вы не думаете при кодировании, почему я это делаю.

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

Answer 5

Беллмана-Форда Алгоритм: кратчайшего пути от источника ко всем другим узлам в весовых ориентированного графа, даже с -eve вес ребра (не цикл). медленнее, но универсальнее, чем Дийсктра. Сложность: O (| V | | Е |.)

BFS: Найти путь от одной вершины к данной другим узлам в ун-взвешенный граф ун-направленный. Сложность: O (| V | + | E |). это быстрее, когда вы знаете вершины вперед и используете соответствующую структуру данных i.е FIFO Que для выяснить, которые уже обработано вершину, чем сложность может быть уменьшен до O (| V |)

DFS: Найти кратчайший путь от источника к другим узлам. в дереве, а также в графе. График может содержать цикл, который означает, что узел можно было бы посещать снова и снова. поэтому мы можем использовать логический массив для отслеживания посещенных узлов. иначе алгоритм не остановится. Более того, он выглядит глубже и глубже и доходит до конца ветки в дереве. Сложность: O (| V | + | E |). и Сложность: O (| V |) пространство для хранения вершин.

Floyed Warshal Алгоритм: Найти все пары кратчайшего пути в графе Directed невзвешенной с + накануне, -eve (не цикл) кромка веса. но он не возвращает детали самих путей. его можно использовать для определения -веса весового цикла в графе. когда он находит один, он заканчивается. он сравнивает весь возможный путь через график между каждой парой вершин. поэтому он использует динамический подход, а не жадный подход. Сложность: O (| V^3 |)

Джонсона Алгоритма: найти все пары кратчайшего пути в взвешенном ориентированном графе разреженного, когда края веса + Ева, -eve, но не -eve цикл. Он сначала использует алгоритм belman-ford для вычисления преобразованного графа из исходного графика. он удаляет -eve веса края. то Дейкстра применяется для поиска путей. Сложность: O (V^2 Вход V + VE)

Дейкстры Алгоритм: оригинальная версия этого алгоритма не использует приоритет Que так Сложность O (| V^2 |) но более новая версия использует эту структуру данных, поэтому сложность становится O (E + V log V). и это более быстрый алгоритм кратчайшего пути с одним источником. он работает, назначая предварительный вес посещаемому узлу и бесконечности для не посещаемых узлов для посещенного узла, который ищет все его нераскрытые края и выбирает с минимальным весом. и добавьте его в набор путей.

Алгоритм Krushkal's:, чтобы найти MST, где он находит край наименьшего возможного веса, который соединяет любые два дерева в лесу с ненаправленным взвешенным графиком. это жадный алгоритм. он также находит минимальный лепесток. Сложность: О (Е лог V)

Алгоритм Прима: он находит подмножество ребер, которые образуют дерево на не направлено, взвешенного графа. но не может найти MS Forest, как алгоритм Крушкала.

Алгоритм Brouvka: Проблема с этим алгоритмом заключается в том, что веса должны быть уникальными в графе. он находит MST, исследуя каждую вершину, а затем помещая ее с меньшим весом. этот алгоритм параллелен природе, но не быстрее, чем алгоритм Прима.

Такая же сложность, как алгоритм Крушкала.