Как теория графов применяется в программировании?

Постоянно вижу, что, чтобы правильно понять основы программирования, нужно знать кучу разделов дискретной математики, в том числе вышеназванную теорию графов. Объясните, пожалуйста, новичку, зачем нужно изучать ее и как и где она применяется.
  • Вопрос задан
  • 14553 просмотра
Пригласить эксперта
Ответы на вопрос 6
sergey-gornostaev
@sergey-gornostaev
Седой и строгий
Прежде всего хочу заметить, что львиная доля программистов не имеют непосредственно дел с теорией и математикой. Можно быть успешным профессионалом, так никогда и не написав собственной реализации алгоритма Дейкстры и даже не имея представления о том, как он работает. Но всё же стоит хотя бы поверхностно познакомится с графами, так как это одна из основных структур данных. Сфера их применения очень обширна, часто это алгоритмы поиска решений - кратчайшего пути по маршруту, эффективного расположения дорожек на схеме, победной игровой стратегии и т.п. Реальный пример использования графов - это sea-of-nodes JIT-компилятора. JIT-компилятор строит граф потока данных и граф потока выполнения, в которых узлы - это инструкции программы, а рёбра - это порядок вызова инструкций и порядок присвоения данных переменным, потом ищет способы этот граф оптимизировать и по оптимизированному графу генерирует бинарный код.

int average(int a, int b) {
  return (a + b) / 2;
}

average.png
Ответ написан
Комментировать
Человек Паук, для новичка программиста при обучении основ программирования в теории графов нет необходимости. Это я Вам говорю, как дипломированный математик прикладник с опытом работы в индустрии разработки ПО.

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

Для новичков, рекомендую "потреблять легкую пищу" при обучении. Основы алгоритмов, методологии программирования (хотя бы императивный подход и ООП), практические навыки работы с инструментами программистов (tooling: IDE, линтеры, VCS, инструменты для сборки и/или упаковщики), технологии (http, ajax, сериализация, ...), ...

Объясните, пожалуйста, новичку, зачем нужно изучать ее и как и где она применяется.

На практике, много где применяется:
  1. Не понимая основ графов, можно запросто запутаться и испортить репозитории в git. Точно так же понадобится для анализа дерева зависимостей и разрешения проблем связанных с ним (смотри).
  2. При отладке программ и профилировании зачастую приходится смотреть AST.
  3. Нахождение путей, определение цикличностей и т.д. понадобятся, когда Ваши данные хорошо подходят для представления в качестве графов. К примеру социальные сети, GPS навигация, множество абстракции в компьютерных играх и т.д.
Ответ написан
Комментировать
@unabl4
ruby on rails web dev
Ну, например, чтобы правильно ответить на собеседовании. :)
Многие компании спрашивают это хотя бы на каком-то базовом уровне.
Вообще, иногда спрашивают классические задачки из Computer Science.
Ну или чтобы успешно выступать на олимпиадах - там это сплошь и рядом.

Пример, который был бы наиболее близок к большенству разработчиков, с чем они сталкиваются каждый день - сборщик зависимостей (package manager, bundler или как угодно называйте) перед компиляцией/запуском.
Идёт построение т.н DAG - https://en.wikipedia.org/wiki/Directed_acyclic_graph , чтобы не было петель.
Ответ написан
Комментировать
@dmitryKovalskiy
программист средней руки
https://habr.com/post/65367/ 30 секунд поисков по запросу "теория графов в программировании". Там кратенько есть применение.
Ответ написан
Комментировать
@Xilian
Программист 1С, сетевые технологии, SQL
Да везде. От построений маршрутов в навигаторов и генерации уровней в играх до расчета себестоимости в той-же 1С.
Ответ написан
Комментировать
@zzzzzzzzzzzzz
Простой пример, который приходит мне в голову - разрешение зависимостей, скажем, при инициализации какого-нибудь приложения. Так, когда компоненты зависят друг от друга, и их нужно подгрузить в правильном порядке, то необходима топологическая сортировка
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы