Информатика • 11 класс
358

Реализация графов (C++)

  • Для реализации графа используется его представление в виде матрицы смежности или в виде списка рёбер и вершин.
  • Для реализации графа все его вершины нумеруются (Рис. А).
  • Наиболее часто используются следующие способы реализации графов:
    • создание матрицы смежности (Рис. Б);
    • создание для каждой вершины списка исходящих из неё рёбер (списка вершин, соединённых с данной вершиной) (Рис. В);
    • создание структуры данных из записей, содержащих данные о рёбрах: номера вершин, которые соединяет ребро, вес, ориентированность (Рис. Г).
  • Способ реализации графа зависит, во-первых, от алгоритма, который будет использован в программе, во-вторых, от самого графа: ориентированный или неориентированный, связный или несвязный и так далее.
Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»