Задачи на графах

Задачи на графах

Задачи на графах

-= заготовка статьи =-
Общим для задач на графах является необходимость их как-то хранить в программе. Для хранения графа [latex] G \left( V, E \right), |V| = n, |E| = m [/latex] в разных случаях используют различные методы. Наиболее популярны из них:

  • Матрица смежности [latex] O \left( n^2 \right) [/latex]
  • Матрица инцидентности [latex] O \left( n \cdot m \right)[/latex]
  • списки рёбер [latex] O \left( m \right)[/latex]

Хорошая идея почитать про алгоритмы на графах здесь и посмотреть решения задач здесь.

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

Решения задач