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

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

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

-= заготовка статьи =-
Общим для задач на графах является необходимость их как-то хранить в программе. Для хранения графа [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]

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

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

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

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)