Реализация графов (Паскаль)

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

Было полезно?